Minimum number of elements to be removed so that pairwise consecutive elements are same
Given a string str. The task is to count the minimum number of elements to be removed so that pairwise consecutive elements are same
Examples:
Input : str = “11344”
Output: 1
Remove the digit 3 from 3rd place so that the string becomes 1144. Thus pairwise two consecutive elements are same. Hence answer is 1.Input : str = “55553”
Output : 1
Remove the digit 3 from the 5th place so that the string becomes 5555. Thus pairwise two consecutive elements are same. Hence answer is 1.
Approach: Check if the current two consecutive elements are same or not. If yes then increment the index by 2 and keep checking till all the elements get traversed. Else increment the index by 1 and count by 1.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to count the minimum number of elements // to remove from a number so that pairwise two // consecutive digits are same. int countConsecutive(string s) { // initialize counting variable int count = 0; for ( int i = 0; i < s.size(); i++) { // check if two consecutive digits are same if (s[i] == s[i + 1]) i++; else count++; } return count; } // Driver code int main() { string str = "44522255" ; cout << countConsecutive(str); return 0; } |
Java
// Java implementation of the above approach class GFG { // Function to count the minimum number of elements // to remove from a number so that pairwise two // consecutive digits are same. static int countConsecutive(String s) { // initialize counting variable int count = 0 ; for ( int i = 0 ; i < s.length(); i++) { // check if two consecutive digits are same if (s.charAt(i) == s.charAt(i + 1 )) { i++; } else { count++; } } return count; } // Driver code public static void main(String args[]) { String str = "44522255" ; System.out.println(countConsecutive(str)); } } // This code is contributed by PrinciRaj19992 |
Python3
# Python 3 implementation of the above approach # Function to count the minimum number of # elements to remove from a number so that # pairwise two consecutive digits are same. def countConsecutive(s): # initialize counting variable count = - 1 for i in range ( len (s) - 1 ): # check if two consecutive # digits are same if (i < = len (s)): if (s[i] is s[i + 1 ]): i + = 1 else : count + = 1 return count # Driver code if __name__ = = '__main__' : str = "44522255" print (countConsecutive( str )) # This code is contributed by PrinciRaj1992 |
C#
// C# implementation of above approach using System; public class GFG { // Function to count the minimum number of elements // to remove from a number so that pairwise two // consecutive digits are same. static int countConsecutive(String s) { // initialize counting variable int count = 0; for ( int i = 0; i < s.Length; i++) { // check if two consecutive digits are same if (s[i] == s[i+1]) { i++; } else { count++; } } return count; } // Driver code public static void Main() { String str = "44522255" ; Console.WriteLine(countConsecutive(str)); } } // This code is contributed by 29AjayKumar |
PHP
<?php // PHP implementation of the above approach // Function to count the minimum number // of elements to remove from a number so // that pairwise two consecutive digits are same. function countConsecutive( $s ) { // initialize counting variable $count = 0; for ( $i = 0; $i < strlen ( $s ); $i ++) { // check if two consecutive // digits are same if ( $s [ $i ] == $s [ $i + 1]) $i ++; else $count ++; } return $count ; } // Driver code $str = "44522255" ; echo countConsecutive( $str ); // This code is contributed by Sachin. ?> |
Javascript
<script> // Javascript implementation of the above approach // Function to count the minimum number of elements // to remove from a number so that pairwise two // consecutive digits are same. function countConsecutive(s) { // initialize counting variable let count = 0; for (let i = 0; i < s.length; i++) { // check if two consecutive digits are same if (s[i] == s[i + 1]) i++; else count++; } return count; } // Driver code let str = "44522255" ; document.write(countConsecutive(str)); // This code is contributed by Surbhi Tyagi. </script> |
2
Time Complexity: O(n), where n is the length of the given string.
Auxiliary Space: O(1)
Contact Us