Given a string str consisting of only two characters ‘a‘ and ‘b‘, the task is to find the minimum steps required to make the string empty by removing consecutive a’s and b’s.
Examples:
Input: str = “bbaaabb”
Output: 2
Explanation:
- Operation 1: Removal of all a’s modifies str to “bbbb”.
- Operation 2: Removal of all remaining b’s makes str empty.
- Therefore, the minimum number of operations required is 2.
Input: str = “aababaa”
Output: 3
Explanation:
- Operation 1: Removal of b’s modifies str to “aaabaa”.
- Operation 2: Removal of b’s modifies str = “aaaaa”.
- Operation 3: Removal of all remaining a’s makes str empty.
- Therefore, the minimum number of operations required is 3.
Approach: This can be solved with the following idea:
The given problem can be solved using Greedy Approach. The idea is to use the count of consecutive sequences of the same character.
Below are the steps involved in the implementation of the code:
- Maintain a counter variable named cnt and initialize it with zero.
- Traverse the given string str and whenever the current character is not equal to its previous character increase cnt by 1. Here we are counting the number of consecutive sequences of the same character.
- At the end, the answer will be (cnt/2 + 1).
Below is the implementation of the code:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum number of// steps requiredint minSteps(string str){ int cnt = 1; for (int i = 1; i < str.size(); i++) { if (str[i] != str[i - 1]) { cnt++; } } // Return the answer return cnt / 2 + 1;}// Driver codeint main(){ string str = "aababaa"; // Function call int ans = minSteps(str); cout << ans; return 0;} |
Java
// JAVA code for the above approachimport java.util.*;class GFG { // Function to find minimum number of // steps required public static int minSteps(String str) { int cnt = 1; for (int i = 1; i < str.length(); i++) { if (str.charAt(i) != str.charAt(i - 1)) { cnt++; } } return cnt / 2 + 1; } // Driver code public static void main(String[] args) { String str = "aababaa"; System.out.println(minSteps(str)); }}// This code is contributed by shivamgupta310570 |
Python3
def minSteps(string): cnt = 1 for i in range(1, len(string)): if string[i] != string[i - 1]: cnt += 1 # Return the answer return cnt // 2 + 1# Driver codeif __name__ == '__main__': string = "aababaa" # Function call ans = minSteps(string) print(ans)# This code is contributed by shivamgupta310570 |
C#
// C# code for the above approachusing System;class GFG{ // Function to find minimum number of // steps required public static int minSteps(string str) { int cnt = 1; for (int i = 1; i < str.Length; i++) { if (str[i] != str[i - 1]) { cnt++; } } return cnt / 2 + 1; } // Driver code public static void Main(string[] args) { string str = "aababaa"; Console.WriteLine(minSteps(str)); }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// Nikunj Sonigara// Function to find minimum number of// steps requiredfunction minSteps(str) { let cnt = 1; for (let i = 1; i < str.length; i++) { if (str[i] !== str[i - 1]) { cnt++; } } return Math.floor(cnt / 2) + 1;}let str = "aababaa";let ans = minSteps(str);console.log(ans); |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
