Leetcode 1234. Replace the Substring for Balanced String

Problem Explanation:

The problem wants us to balance a string consisting only of four distinct characters, 'Q', 'W', 'E' and 'R'. The string will be considered balanced if each character appears exactly n/4 times, where n is the length of the string.

The problem asks us to find the minimum length of a substring that we can replace to make the original string balanced.

Example Walkthrough:

We take an example string "QQER". In the string, 'Q' appears twice whereas 'W' does not appear. So, we can replace one 'Q' with 'W' to make the string balanced. Hence, the length of the substring is '1'.

Approach to the Solution:

Firstly, the '128 size vector' is used to store the count of the four characters from the string s.

The for loop that follows counts the occurrence of each character.

The next for loop is used to find a window where all counts are exceeding n/4 as 'j' is incremented.

After finding such window, we start to minimize it by moving 'i' and 'j' towards right till the time all counts are still greater than n/4.

The size of this minimized window is the minimum length of the substring that we need to replace to balance the original string s.

The approach takes advantage of two pointers and moves from left to right in a window, which is a common pattern in solving such kind of problems.

C++ Solution:

1
2cpp
3class Solution {
4 public:
5  int balancedString(string s) {
6    const int n = s.length();
7    const int k = n / 4;
8    int ans = n;
9    vector<int> count(128);
10
11    // Count occurrence of each character in the string
12    for (const char c : s)
13      ++count[c];
14
15    // Move i and j towards right and minimize the window
16    for (int i = 0, j = 0; i < n; ++i) {
17      --count[s[i]]; 
18      while (j < n && count['Q'] <= k && count['W'] <= k && count['E'] <= k &&
19             count['R'] <= k) {
20        ans = min(ans, i - j + 1); // Calculate length of substring
21        ++count[s[j]];
22        ++j;
23      }
24    }
25    // Return minimum length of substring to replace
26    return ans;
27  }
28};

Java Solution:

1
2java
3class Solution {
4    public int balancedString(String s) {
5        int[] count = new int[128];
6        int n = s.length(), k = n / 4, res = n;
7        for (int i = 0; i < n; ++i) {
8            ++count[s.charAt(i)];
9        }
10        for (int i = 0, j = 0; i < n; ++i) {
11            --count[s.charAt(i)];
12            while (j < n && count['Q'] <= k && count['W'] <= k && count['E'] <= k && count['R'] <= k) {
13                res = Math.min(res, i - j + 1);
14                ++count[s.charAt(j++)];
15            }
16        }
17        return res;
18    }
19}

Python Solution:

1
2python
3class Solution:
4    def balancedString(self, s: str) -> int:
5        c = collections.Counter(s)
6        n, i, min_len = len(s), 0, len(s)
7        for j, ch in enumerate(s):
8            c[ch] -= 1
9            while all(n / 4 >= c[ch] for ch in 'QWER'):
10                min_len = min(min_len, j - i + 1)
11                c[s[i]] += 1
12                i += 1
13        return min_len

Javascript Solution:

1
2js
3var balancedString = function(s) {
4    let len = s.length, k = len >> 2, count = new Array(128).fill(0), res = len;
5    for (let i = 0; i < len; ++i) {
6        ++count[s.charCodeAt(i)];
7    }
8    for (let i = 0, j = 0; i < len; ++i) {
9        --count[s.charCodeAt(i)];
10        while (j < len && count['Q'.charCodeAt(0)] <= k && count['W'.charCodeAt(0)] <= k &&
11               count['E'.charCodeAt(0)] <= k && count['R'.charCodeAt(0)] <= k) {
12            res = Math.min(res, i - j + 1);
13            ++count[s.charCodeAt(j++)];
14        }
15    }
16    return res;
17};

C# Solution:

1
2csharp
3public class Solution {
4    public int BalancedString(string s) {
5        int n = s.Length;
6        int k = n / 4;
7        int ans = n;
8        int[] count = new int[128];
9
10        foreach (char c in s)
11            ++count[c];
12
13        for (int i = 0, j = 0; i < n; ++i) {
14            --count[s[i]];
15            while (j < n && count['Q'] <= k && count['W'] <= k && count['E'] <= k && count['R'] <= k) {
16                ans = Math.Min(ans, i - j + 1);
17                ++count[s[j]];
18                ++j;
19            }
20        }
21        return ans;
22    }
23}

Each of the solutions provided above accurately uses the same approach and algorithm to solve the problem in their respective languages. The problem is effectively solved by using a sliding window technique with two pointers to minimize the window than contains counts of 'Q', 'W', 'E', and 'R' that are greater than n/4. The minimum length of this window is returned as the result.## Kotlin Solution:

1
2kotlin
3class Solution {
4    fun balancedString(s: String): Int {
5        val n = s.length
6        val k = n / 4
7        val count = IntArray(128)
8
9        for (char in s)
10            ++count[char.toInt()]
11        
12        var j = 0
13        var minLen = n
14        for (i in s.indices) {
15            --count[s[i].toInt()]
16            while (j < n && count['Q'.toInt()] <= k &&
17                   count['W'.toInt()] <= k && count['E'.toInt()] <= k && count['R'.toInt()] <= k) {
18                minLen = minOf(minLen, i - j + 1)
19                ++count[s[j].toInt()]
20                ++j
21            }
22        }
23        return minLen
24    }
25}

This Kotlin solution also solves the problem using the same approach. It first creates an integer array to store the ASCII representations of the characters in the string. Then it balances the string by replacing a substring with another substring and returns the minimum legnth of that substring. The method uses two pointers: i and j. The i pointer moves through the string, while the j pointer moves only when the string becomes balanced.

TypeScript Solution

1
2typescript
3function balancedString(s: string): number {
4    const n = s.length, k = n / 4, count = new Array(128).fill(0);
5    let res = n;
6    for (let i = 0; i < n; ++i) {
7        ++count[s.charCodeAt(i)];
8    }
9    for (let i = 0, j = 0; i < n; ++i) {
10        --count[s.charCodeAt(i)];
11        while (j < n && count['Q'.charCodeAt(0)] <= k && count['W'.charCodeAt(0)] <= k &&
12            count['E'.charCodeAt(0)] <= k && count['R'.charCodeAt(0)] <= k) {
13            res = Math.min(res, i - j + 1);
14            ++count[s.charCodeAt(j++)];
15        }
16    }
17    return res;
18};

This TypeScript solution offers the same approach of using two pointers and a greedy approach to keep track of characters and their counts. The function uses a JavaScript while loop, where all four characters (Q, W, E, and R) are checked against the quarter value of string length k. When the current character count is below or equals to k, the loop reduces substring length and increase the counter of j, until when current character count exceeds k and the loop break and move i.

These solutions in different programming languages, provide an efficient and easy understand way to solve the balanced string problem using a two pointer sliding window technique.