Given a string str of length N (divisible by 3) consisting of atmost three distinct characters, the task is to find the length of the smallest substring whose characters can be replaced so that each character occurs exactly N/3 times.
Examples:
Input: str = “ABB”
Output: 1
Explanation: One optimal way is to replace the substring “B” with any character, suppose “C”.
Hence, the resulting is “ABC” having frequency of each character as N/3.Input: str = “ABCBBB”
Output: 2
Approach: The given problem can be solved using the sliding window technique. Since the frequency of each character should be N/3, hence the number of excess occurrences of the characters can be calculated. The idea is to find the length of the smallest substring such that it contains all the excess characters which can then be replaced. Below are the steps to follow:
- Create a map, extraChars which stores the characters in str that appear more than N/3 times along with their respective excess count.
- Use sliding window to find the shortest substring that has all characters in extraChar with the given frequency. It can be done similarly as discussed in the problem of finding the smallest substring which contains all characters of another string.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h> using namespace std; int balanceString(string str) { int N = str.length(); // If length of str is 0 if (N == 0) { return 0; } // Stores the frequency of // each char in str map< char , int > strFreq; for ( char ch : str) strFreq[ch]++; // Stores the characters having // excess occurrences with count map< char , int > extraChars; for ( auto ch : strFreq) { // If there are more than N/3 // characters in the string str if (ch.second > N / 3) extraChars[ch.first] = (ch.second - N / 3); } // If no characters occurs more // than N/3 time in the string if (extraChars.size() == 0) { return 0; } // Represents start of the window, // end of the window and the // required answer respectively int i = 0, j = 0; int minWindowLength = N + 1; // Stores the number of unique // characters to in substring int count = extraChars.size(); while (j < N) { // Store current character char ch = str[j]; // Check if c is an excess char if (extraChars.find(ch) != extraChars.end()) { // Reduce Count extraChars[ch]--; // If window has the // required count if (extraChars[ch] == 0) count--; } // If current window has all char if (count == 0) { // Reduce Window size while (i < N && count == 0) { // Update the minimum // length of window minWindowLength = min(minWindowLength, j - i + 1); // If character at index // i is an excess char if (extraChars.find(str[i]) != extraChars.end()) { // Update frequency extraChars[str[i]]++; // Update Count if (extraChars[str[i]] == 1) count++; } i++; } } j++; } return minWindowLength; } // Driver Code int main() { string str = "ABCBBB" ; cout << balanceString(str); return 0; } // This code is contributed by hrithikgarg03188 |
Java
// Java code to implement above approach import java.io.*; import java.util.*; class GFG { static int balanceString(String str) { int N = str.length(); // If length of str is 0 if (N == 0 ) { return 0 ; } // Stores the frequency of // each char in str HashMap<Character, Integer> strFreq = new HashMap<>(); for ( char c : str.toCharArray()) strFreq.put(c, strFreq.getOrDefault(c, 0 ) + 1 ); // Stores the characters having // excess occurrences with count HashMap<Character, Integer> extraChars = new HashMap<>(); for ( char c : strFreq.keySet()) { // If there are more than N/3 // characters in the string str if (strFreq.get(c) > N / 3 ) extraChars.put(c, strFreq.get(c) - N / 3 ); } // If no characters occurs more // than N/3 time in the string if (extraChars.size() == 0 ) { return 0 ; } // Represents start of the window, // end of the window and the // required answer respectively int i = 0 , j = 0 ; int minWindowLength = N + 1 ; // Stores the number of unique // characters to in substring int count = extraChars.size(); while (j < N) { // Store current character char c = str.charAt(j); // Check if c is an excess char if (extraChars.containsKey(c)) { // Reduce Count extraChars.put(c, extraChars.get(c) - 1 ); // If window has the // required count if (extraChars.get(c) == 0 ) count--; } // If current window has all char if (count == 0 ) { // Reduce Window size while (i < N && count == 0 ) { // Update the minimum // length of window minWindowLength = Math.min(minWindowLength, j - i + 1 ); // If character at index // i is an excess char if (extraChars.containsKey( str.charAt(i))) { // Update frequency extraChars.put( str.charAt(i), extraChars.get( str.charAt(i)) + 1 ); // Update Count if (extraChars.get( str.charAt(i)) == 1 ) count++; } i++; } } j++; } return minWindowLength; } // Driver Code public static void main(String[] args) { String str = "ABCBBB" ; System.out.println(balanceString(str)); } } |
Python3
# python3 code for the above approach def balanceString( str ): N = len ( str ) # If length of str is 0 if (N = = 0 ): return 0 # Stores the frequency of # each char in str strFreq = {} for c in str : strFreq = strFreq + 1 if c in strFreq else 1 # Stores the characters having # excess occurrences with count extraChars = {} for c in strFreq: # If there are more than N/3 # characters in the string str if (strFreq > N / / 3 ): extraChars = (strFreq - N / / 3 ) # If no characters occurs more # than N/3 time in the string if ( len (extraChars) = = 0 ): return 0 # Represents start of the window, # end of the window and the # required answer respectively i, j = 0 , 0 minWindowLength = N + 1 # Stores the number of unique # characters to in substring count = len (extraChars) while (j < N): # Store current character c = str [j] # Check if c is an excess char if (c in extraChars): # Reduce Count extraChars - = 1 # If window has the # required count if (extraChars = = 0 ): count - = 1 # If current window has all char if (count = = 0 ): # Reduce Window size while (i < N and count = = 0 ): # Update the minimum # length of window minWindowLength = min (minWindowLength, j - i + 1 ) # If character at index # i is an excess char if ( str [i] in extraChars): # Update frequency extraChars[ str [i]] + = 1 # Update Count if (extraChars[ str [i]] = = 1 ): count + = 1 i + = 1 j + = 1 return minWindowLength # Driver Code if __name__ = = "__main__" : str = "ABCBBB" print (balanceString( str )) # This code is contributed by rakeshsahni |
C#
// Java code to implement above approach using System; using System.Collections.Generic; class GFG { static int balanceString( string str) { int N = str.Length; // If length of str is 0 if (N == 0) { return 0; } // Stores the frequency of // each char in str Dictionary< char , int > strFreq = new Dictionary< char , int >(); foreach ( char c in str.ToCharArray()) { if (strFreq.ContainsKey(c)) strFreq += 1; else strFreq = 1; } // Stores the characters having // excess occurrences with count Dictionary< char , int > extraChars = new Dictionary< char , int >(); foreach (KeyValuePair< char , int > c in strFreq) { // If there are more than N/3 // characters in the string str if (c.Value > N / 3) extraChars = c.Value - N / 3; } // If no characters occurs more // than N/3 time in the string if (extraChars.Count == 0) { return 0; } // Represents start of the window, // end of the window and the // required answer respectively int i = 0, j = 0; int minWindowLength = N + 1; // Stores the number of unique // characters to in substring int count = extraChars.Count; while (j < N) { // Store current character char c = str[j]; // Check if c is an excess char if (extraChars.ContainsKey(c)) { // Reduce Count extraChars -= 1; // If window has the // required count if (extraChars == 0) count--; } // If current window has all char if (count == 0) { // Reduce Window size while (i < N && count == 0) { // Update the minimum // length of window minWindowLength = Math.Min( minWindowLength, j - i + 1); // If character at index // i is an excess char if (extraChars.ContainsKey(str[i])) { // Update frequency extraChars[str[i]] += 1; // Update Count if (extraChars[str[i]] == 1) count++; } i++; } } j++; } return minWindowLength; } // Driver Code public static void Main() { string str = "ABCBBB" ; Console.WriteLine(balanceString(str)); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach function balanceString(str) { let N = str.length; // If length of str is 0 if (N == 0) { return 0; } // Stores the frequency of // each char in str let strFreq = new Map(); str = str.split( '' ) for (let c of str) { if (strFreq.has(c)) strFreq.set(c, strFreq.get(c) + 1); else strFreq.set(c, 1) } str = str.join( '' ) // Stores the characters having // excess occurrences with count let extraChars = new Map(); for (let c of strFreq.keys()) { // If there are more than N/3 // characters in the string str if (strFreq.get(c) > Math.floor(N / 3)) extraChars.set(c, strFreq.get(c) - Math.floor(N / 3)); } // If no characters occurs more // than N/3 time in the string if (extraChars.size == 0) { return 0; } // Represents start of the window, // end of the window and the // required answer respectively let i = 0, j = 0; let minWindowLength = N + 1; // Stores the number of unique // characters to in substring let count = extraChars.size; while (j < N) { // Store current character let c = str.charAt(j); // Check if c is an excess char if (extraChars.has(c)) { // Reduce Count extraChars.set(c, extraChars.get(c) - 1); // If window has the // required count if (extraChars.get(c) == 0) count--; } // If current window has all char if (count == 0) { // Reduce Window size while (i < N && count == 0) { // Update the minimum // length of window minWindowLength = Math.min(minWindowLength, j - i + 1); // If character at index // i is an excess char if (extraChars.has( str.charAt(i))) { // Update frequency extraChars.set( str.charAt(i), extraChars.get( str.charAt(i)) + 1); // Update Count if (extraChars.get( str.charAt(i)) == 1) count++; } i++; } } j++; } return minWindowLength; } // Driver Code let str = "ABCBBB" ; document.write(balanceString(str)); // This code is contributed by Potta Lokesh </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!