Replace The Substring For Balanced String - Leetcode Solution

Problem Statement

You are given a string s containing only characters 'Q', 'W', 'E', and 'R'. Find the minimum length of a substring of s that we can replace with any string of the same length such that the resulting string s becomes a "balanced" string.

A string is "balanced" if each character in the string appears exactly n/4 times, where n is the length of the string.

Example

Input: s = "QWER" Output: 0

Input: s = "QQWE" Output: 1

Input: s = "QQQW" Output: 2

Input: s = "QQQQ" Output: 3

Solution

Approach:

• To get a "balanced" string, the substring that needs to be replaced should contain only the characters that occur more than n/4 times.
• We first need to calculate the frequency of each character in the given string.
• Then, we can use a sliding window of length l to check whether there is a substring of length l that contains only the characters that occur more than n/4 times.
• We keep moving the window until we find the minimum length substring that needs to be replaced.
• To make the implementation efficient, we can use two pointers (left and right) to keep track of the substring that we are verifying, and use a counter to keep track of the frequency of each character in the substring.

Algorithm:

• Count the frequency of each character in the string s.

• Check if the frequency of each character in s is less than or equal to n/4. If yes, return 0.

• Initialize left and right pointers to 0. Initialize a variable min_len to n.

• Iterate over the string s using the right pointer:

• Increment the frequency counter for the character s[right].

• If the substring [left, right] is "balanced" (i.e. contains only characters that appear at most n/4 times), move the left pointer to the right until the substring is no longer "balanced".

• If the substring [left, right] has more characters than needed to make it "balanced", update the min_len with the length of the substring.

• If the frequency counter for any character in the string s is less than n/4, terminate the loop.

• Return min_len.

Time Complexity:

• The frequency counting step takes O(n) time. The sliding window iteration takes O(n) time in the worst case. Therefore, the overall time complexity of the algorithm is O(n).

Space Complexity:

• The space complexity of the algorithm is O(1), as we are only using a constant amount of extra memory to store the frequency counters and the pointers.

1