Minimum number of deletions so that no two consecutive are same
Given a string, find minimum number of deletions required so that there will be no two consecutive repeating characters in the string.
Examples:
Input : AAABBB Output : 4 Explanation : New string should be AB Input : ABABABAB Output : 0 Explanation : There are no consecutive repeating characters.
If there are n consecutive same characters delete n-1 out of those n characters.
Algorithm:
- Define a function countDeletions that takes a string str as input and returns an integer.
- Initialize a variable ans to 0.
- Iterate over the string str from the first character till the second last character:
a. If the current character and the next character are the same, increment ans by 1. - Return ans as the minimum number of deletions required.
Pseudocode:
function countDeletions(str): ans = 0 for i from 0 to length(str)-2: if str[i] == str[i+1]: ans++ return ans
Implementation:
C++
// CPP code to count minimum deletions required // so that there are no consecutive characters left #include <bits/stdc++.h> using namespace std; int countDeletions(string str) { int ans = 0; for ( int i = 0; i < str.length() - 1; i++) // If two consecutive characters are // the same, delete one of them. if (str[i] == str[i + 1]) ans++; return ans; } // Driver code int main() { string str = "AAABBB" ; // Function call to print answer cout << countDeletions(str); return 0; } |
Java
// Java code to count minimum deletions required // so that there are no consecutive characters left import java.util.*; class GFG { static int countDeletions(String s) { int ans = 0 ; char [] str = s.toCharArray(); for ( int i = 0 ; i < str.length - 1 ; i++) // If two consecutive characters are // the same, delete one of them. if (str[i] == str[i + 1 ]) ans++; return ans; } // Driver code public static void main(String[] args) { String str = "AAABBB" ; // Function call to print answer System.out.println(countDeletions(str)); } } /* This code is contributed by Mr. Somesh Awasthi */ |
Python3
# Python code to count minimum deletions required # so that there are no consecutive characters left\ def countDeletions(string): ans = 0 for i in range ( len (string) - 1 ): # If two consecutive characters are # the same, delete one of them. if (string[i] = = string[i + 1 ]): ans + = 1 return ans # Driver code string = "AAABBB" # Function call to print answer print (countDeletions(string)) # This code is contributed by Sachin Bisht |
C#
// C# Program to count minimum deletions // required so that there are no // consecutive characters left using System; class GFG { // Function for counting deletions static int countDeletions(String s) { int ans = 0; char []str = s.ToCharArray(); for ( int i = 0; i < str.Length - 1; i++) // If two consecutive characters are // the same, delete one of them. if (str[i] == str[i + 1]) ans++; return ans; } // Driver code public static void Main() { String str = "AAABBB" ; // Function call to print answer Console.Write(countDeletions(str)); } } // This code is contributed by Nitin Mittal. |
PHP
<?php // PHP code to count minimum // deletions required so that // there are no consecutive // characters left function countDeletions( $str ) { $ans = 0; for ( $i = 0; $i < strlen ( $str ) - 1; $i ++) // If two consecutive characters are // the same, delete one of them. if ( $str [ $i ] == $str [ $i + 1]) $ans ++; return $ans ; } // Driver Code $str = "AAABBB" ; // Function call to // print answer echo countDeletions( $str ); // This code is contributed by nitin mittal ?> |
Javascript
<script> // javascript code to count minimum deletions required // so that there are no consecutive characters left function countDeletions(s) { var ans = 0; var str = s; for ( var i = 0; i < str.length - 1; i++) // If two consecutive characters are // the same, delete one of them. if (str[i] == str[i + 1]) ans++; return ans; } // Driver code var str = "AAABBB" ; // Function call to print answer document.write(countDeletions(str)); // This code is contributed by gauravrajput1 </script> |
Output
4