1234. Replace the Substring for Balanced String Solution

Q: Is Replace the Substring for Balanced String easy or hard?

Replace the Substring for Balanced String is considered a medium difficulty problem. The challenge comes from recognizing that the substring to replace can be found using a sliding window instead of checking all substrings, which would lead to a slower O(n^2) solution.

Q: Replace the Substring for Balanced String Python/Java solution

Python and Java implementations typically maintain a hash map or array of size four for character counts and use two pointers to represent the sliding window. The algorithm scans the string once, updating counts and shrinking the window when the balance condition is met, giving O(n) time complexity.

Q: How to solve Replace the Substring for Balanced String in O(n)?

First count occurrences of Q, W, E, and R. Use a sliding window and move the right pointer across the string while decreasing counts for characters inside the window. Whenever the remaining counts outside the window are all less than or equal to n/4, move the left pointer to shrink the window and update the minimum length.

Q: What is the best approach for Replace the Substring for Balanced String?

The optimal approach uses a sliding window with a frequency counter. Count how many times each character appears and track characters exceeding n/4. Expand a window and reduce counts for characters inside the window until the remaining string becomes balanced. This produces an O(n) time solution with O(1) space.

Q: Is Replace the Substring for Balanced String asked at Google/Amazon/Meta?

Replace the Substring for Balanced String appears in many company-tagged interview preparation lists for large tech companies. Variants of sliding window string balancing problems are commonly asked in interviews at companies like Amazon, Google, and Meta because they test frequency counting and window optimization.

Q: What data structure is used in Replace the Substring for Balanced String?

The solution mainly uses a frequency map or fixed-size array to count characters. Combined with two pointers forming a sliding window, it efficiently tracks how many characters remain outside the window and whether the balance condition is satisfied.

Q: What is the time complexity of Replace the Substring for Balanced String?

The optimal sliding window solution runs in O(n) time because each pointer moves across the string at most once. The space complexity is O(1) since only four character counts (Q, W, E, R) are tracked regardless of input size.

The problem

You are given a string s of length n containing only four kinds of characters: 'Q', 'W', 'E', and 'R'.

A string is said to be balanced if each of its characters appears n / 4 times where n is the length of the string.

Return the minimum length of the substring that can be replaced with any other string of the same length to make s balanced. If s is already balanced, return 0.

Example 1:

Input: s = "QWER"
Output: 0
Explanation: s is already balanced.

Example 2:

Input: s = "QQWE"
Output: 1
Explanation: We need to replace a 'Q' to 'R', so that "RQWE" (or "QRWE") is balanced.

Example 3:

Input: s = "QQQW"
Output: 2
Explanation: We can replace the first "QQ" to "ER".

Constraints:

n == s.length
4 <= n <= 10⁵
n is a multiple of 4.
s contains only 'Q', 'W', 'E', and 'R'.

Approach overview

Problem Overview: You get a string containing only Q, W, E, and R. A string is balanced when each character appears exactly n/4 times. The task is to find the minimum length substring you can replace so the remaining string becomes balanced.

Approach 1: Sliding Window Approach (O(n) time, O(1) space)

This approach uses a frequency counter and a dynamic window to track which substring could be replaced. First count how many times each character appears. Any character exceeding n/4 is considered extra. Expand a right pointer to include characters in the window and decrease their counts from the outside frequency map. Once all remaining characters outside the window satisfy the balanced condition (count[c] ≤ n/4), shrink the window using the left pointer to minimize its length. Because each index moves at most once, the total time complexity is O(n) and the space complexity is O(1). This method relies on the classic sliding window pattern combined with frequency counting.

Approach 2: Two-Pointer Technique (O(n) time, O(1) space)

The two-pointer technique frames the same idea more explicitly: maintain left and right pointers that represent the candidate substring to replace. As right moves forward, update counts for characters leaving the "outside" portion of the string. When the outside portion becomes valid (no character exceeds n/4), move left forward to shrink the window while updating the minimum length. This method still scans the string only once and uses a constant-size frequency array because the alphabet is fixed. The approach is closely related to both two pointers and sliding window patterns used in many string optimization problems.

Recommended for interviews: Interviewers expect the Sliding Window solution. A brute force approach that tries all substrings would be O(n^2) and fails for large inputs. Demonstrating the window technique shows you understand how to maintain constraints dynamically while scanning the string in linear time.

Approach 1: Sliding Window Approach

The sliding window technique is ideal for problems involving substrings or adding elements to arrays incrementally. Here, we'll form a window which slides over the string until each possible character's frequency is less than or equal to n/4, starting from the beginning of the string and moving rightwards.

Python

def balancedString(s):
    from collections import Counter

    n = len(s) // 4
    count = Counter(s)
    result, start = len(s), 0
    for end, char in enumerate(s):
        count[char] -= 1
        while all(count[x] <= n for x in 'QWER'):
            result = min(result, end - start + 1)
            count[s[start]] += 1
            start += 1
    return result

print(balancedString("QQWERR"))

Java

import java.util.HashMap;

public class Solution {
    public int balancedString(String s) {
        int len = s.length();
        int n = len / 4;
        HashMap<Character, Integer> count = new HashMap<>();
        for (char c : s.toCharArray()) count.put(c, count.getOrDefault(c, 0) + 1);
        if (count.get('Q') == n && count.get('W') == n && count.get('E') == n && count.get('R') == n) return 0;
        int result = len;
        for (int start = 0, end = 0; end < len; end++) {
            count.put(s.charAt(end), count.get(s.charAt(end)) - 1);
            while (count.get('Q') <= n && count.get('W') <= n && count.get('E') <= n && count.get('R') <= n) {
                result = Math.min(result, end - start + 1);
                count.put(s.charAt(start), count.get(s.charAt(start)) + 1);
                start++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.balancedString("QQWERR"));
    }
}

C++

#include <iostream>
#include <unordered_map>
using namespace std;

int balancedString(string s) {
    int len = s.size();
    int n = len / 4;
    unordered_map<char, int> count;
    for (char c : s) count[c]++;
    if (count['Q'] == n && count['W'] == n && count['E'] == n && count['R'] == n) return 0;
    int result = len;
    for (int start = 0, end = 0; end < len; end++) {
        count[s[end]]--;
        while (count['Q'] <= n && count['W'] <= n && count['E'] <= n && count['R'] <= n) {
            result = min(result, end - start + 1);
            count[s[start++]]++;
        }
    }
    return result;
}

int main() {
    cout << balancedString("QQWERR") << endl;
    return 0;
}

JavaScript

function balancedString(s) {
    const n = s.length / 4;
    const count = {'Q': 0, 'W': 0, 'E': 0, 'R': 0};
    for (let c of s) count[c]++;
    const isBalanced = () => Object.values(count).every(value => value <= n);
    let result = s.length, start = 0;
    for (let end = 0; end < s.length; end++) {
        count[s[end]]--;
        while (isBalanced()) {
            result = Math.min(result, end - start + 1);
            count[s[start++]]++;
        }
    }
    return result;
}

console.log(balancedString("QQWERR"));

#include <stdio.h>
#include <string.h>

int balancedString(char* s) {
    int len = strlen(s);
    int n = len / 4;
    int count[128] = {0};
    for (int i = 0; i < len; i++) count[s[i]]++;
    if (count['Q'] == n && count['W'] == n && count['E'] == n && count['R'] == n) return 0;
    int result = len;
    for (int start = 0, end = 0; end < len; end++) {
        count[s[end]]--;
        while (count['Q'] <= n && count['W'] <= n && count['E'] <= n && count['R'] <= n) {
            result = (result < end - start + 1) ? result : end - start + 1;
            count[s[start++]]++;
        }
    }
    return result;
}

int main() {
    char s[] = "QQWERR";
    printf("%d\n", balancedString(s));
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int BalancedString(string s) {
        int n = s.Length / 4;
        Dictionary<char, int> count = new Dictionary<char, int>();
        foreach (var ch in s) {
            if (!count.ContainsKey(ch)) count[ch] = 0;
            count[ch]++;
        }
        if (count['Q'] == n && count['W'] == n && count['E'] == n && count['R'] == n) return 0;
        int result = s.Length, start = 0;
        for (int end = 0; end < s.Length; end++) {
            count[s[end]]--;
            while (count['Q'] <= n && count['W'] <= n && count['E'] <= n && count['R'] <= n) {
                result = Math.Min(result, end - start + 1);
                count[s[start]]++;
                start++;
            }
        }
        return result;
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.BalancedString("QQWERR")); 
    }
}

This Python solution is concise and utilizes a Counter to keep track of character frequencies while employing a dynamic sliding window to minimize the substring size.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Two-Pointer Technique

This approach increases string traversal efficiency by using two pointers to monitor segment boundaries, overflowing initially until satisfied by frequency and effectively reducing substring lengths by adjusting inward.

Python

from collections import Counter

def balancedString(s):
    n = len(s) // 4
    count = Counter(s)
    excess = {ch: count[ch] - n for ch in 'QWER'}
    result, start = len(s), 0
    for end, char in enumerate(s):
        count[char] -= 1
        while all(count[x] >= excess[x] for x in 'QWER'):
            result = min(result, end - start + 1)
            count[s[start]] += 1
            start += 1
    return result

print(balancedString("QQWERR"))

Java

import java.util.HashMap;

public class Solution {
    public int balancedString(String s) {
        int len = s.length();
        int n = len / 4;
        HashMap<Character, Integer> count = new HashMap<>();
        for (char c : s.toCharArray()) {
            count.put(c, count.getOrDefault(c, 0) + 1);
        }
        int excessQ = count.get('Q') - n;
        int excessW = count.get('W') - n;
        int excessE = count.get('E') - n;
        int excessR = count.get('R') - n;
        int result = len, start = 0;
        for (int end = 0; end < len; end++) {
            count.put(s.charAt(end), count.get(s.charAt(end)) - 1);
            while (count.get('Q') >= excessQ && count.get('W') >= excessW && count.get('E') >= excessE && count.get('R') >= excessR) {
                result = Math.min(result, end - start + 1);
                count.put(s.charAt(start), count.get(s.charAt(start)) + 1);
                start++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.balancedString("QQWERR")); 
    }
}

C++

#include <iostream>
#include <unordered_map>
using namespace std;

int balancedString(string s) {
    int len = s.size();
    int n = len / 4;
    unordered_map<char, int> count;
    for (char c : s) count[c]++;
    unordered_map<char, int> excess = {{'Q',count['Q'] - n}, {'W',count['W'] - n}, {'E',count['E'] - n}, {'R',count['R'] - n}};
    int result = len;
    for (int start = 0, end = 0; end < len; end++) {
        count[s[end]]--;
        while (excess['Q'] <= count['Q'] && excess['W'] <= count['W'] && excess['E'] <= count['E'] && excess['R'] <= count['R']) {
            result = min(result, end - start + 1);
            count[s[start++]]++;
        }
    }
    return result;
}

int main() {
    cout << balancedString("QQWERR") << endl;
    return 0;
}

JavaScript

function balancedString(s) {
    const n = s.length / 4;
    const count = {'Q': 0, 'W': 0, 'E': 0, 'R': 0};
    for (let c of s) count[c]++;
    const excess = {'Q': count['Q'] - n, 'W': count['W'] - n, 'E': count['E'] - n, 'R': count['R'] - n};
    let result = s.length, start = 0;
    for (let end = 0; end < s.length; end++) {
        count[s[end]]--;
        let allBalanced = true;
        for (const ch in excess) {
            if (excess[ch] > count[ch]) {
                allBalanced = false;
                break;
            }
        }
        while (allBalanced) {
            result = Math.min(result, end - start + 1);
            count[s[start++]]++;
            allBalanced = true;
            for (const ch in excess) {
                if (excess[ch] > count[ch]) {
                    allBalanced = false;
                    break;
                }
            }
        }
    }
    return result;
}

console.log(balancedString("QQWERR"));

#include <stdio.h>
#include <string.h>

int balancedString(char* s) {
    int len = strlen(s);
    int n = len / 4;
    int count[128] = {0};
    for (int i = 0; i < len; i++) count[s[i]]++;
    int excess[4] = {count['Q'] - n, count['W'] - n, count['E'] - n, count['R'] - n};
    int result = len;
    for (int start = 0, end = 0; end < len; end++) {
        count[s[end]]--;
        while (excess[0] <= count['Q'] && excess[1] <= count['W'] && excess[2] <= count['E'] && excess[3] <= count['R'] && start < len) {
            result = result < end - start + 1 ? result : end - start + 1;
            count[s[start++]]++;
        }
    }
    return result;
}

int main() {
    char s[] = "QQWERR";
    printf("%d\n", balancedString(s));
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int BalancedString(string s) {
        int n = s.Length / 4;
        Dictionary<char, int> count = new Dictionary<char, int>();
        foreach (var ch in s) {
            if (!count.ContainsKey(ch)) count[ch] = 0;
            count[ch]++;
        }
        int[] excess = {count['Q'] - n, count['W'] - n, count['E'] - n, count['R'] - n};
        int result = s.Length, start = 0;
        for (int end = 0; end < s.Length; end++) {
            count[s[end]]--;
            while (excess[0] <= count['Q'] && excess[1] <= count['W'] && excess[2] <= count['E'] && excess[3] <= count['R'] && start < s.Length) {
                result = Math.Min(result, end - start + 1);
                count[s[start]]++;
                start++;
            }
        }
        return result;
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.BalancedString("QQWERR")); 
    }
}

This Python function tracks character excess at each roll of the window, then reframes possible candidates needed with dual pointers until achieving a minimal section. It optimizes space but efficiently checks each end point.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Counting + Two Pointers

First, we use a hash table or array cnt to count the number of each character in string s. If the count of all characters does not exceed n/4, then the string s is balanced, and we directly return 0.

Otherwise, we use two pointers j and i to maintain the left and right boundaries of the window, initially j = 0.

Next, we traverse the string s from left to right. Each time we encounter a character, we decrease its count by 1, then we check whether the current window meets the condition, that is, the count of characters outside the window does not exceed n/4. If the condition is met, we update the answer, then move the left boundary of the window to the right until the condition is not met.

Finally, we return the answer.

The time complexity is O(n), and the space complexity is O(C). Where n is the length of the string s; and C is the size of the character set, in this problem C = 4.

func balancedString(s string) int {
	cnt := [4]int{}
	t := "QWER"
	n := len(s)
	for i := range s {
		cnt[strings.IndexByte(t, s[i])]++
	}
	m := n / 4
	if cnt[0] == m && cnt[1] == m && cnt[2] == m && cnt[3] == m {
		return 0
	}
	ans := n
	for i, j := 0, 0; i < n; i++ {
		cnt[strings.IndexByte(t, s[i])]--
		for j <= i && cnt[0] <= m && cnt[1] <= m && cnt[2] <= m && cnt[3] <= m {
			ans = min(ans, i-j+1)
			cnt[strings.IndexByte(t, s[j])]++
			j++
		}
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sliding Window Approach	Time Complexity: O(n) Space Complexity: O(1)
Two-Pointer Technique	Time Complexity: O(n) Space Complexity: O(1)
Counting + Two Pointers	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Substring Check	O(n^2)	O(1)	Conceptual understanding or very small inputs
Sliding Window with Frequency Count	O(n)	O(1)	Optimal solution for large strings and interview settings
Two-Pointer Technique	O(n)	O(1)	Alternative implementation of the same window idea with explicit pointers

Frequently asked questions

Is Replace the Substring for Balanced String easy or hard?

Replace the Substring for Balanced String is considered a medium difficulty problem. The challenge comes from recognizing that the substring to replace can be found using a sliding window instead of checking all substrings, which would lead to a slower O(n^2) solution.

Replace the Substring for Balanced String Python/Java solution

Python and Java implementations typically maintain a hash map or array of size four for character counts and use two pointers to represent the sliding window. The algorithm scans the string once, updating counts and shrinking the window when the balance condition is met, giving O(n) time complexity.

How to solve Replace the Substring for Balanced String in O(n)?

First count occurrences of Q, W, E, and R. Use a sliding window and move the right pointer across the string while decreasing counts for characters inside the window. Whenever the remaining counts outside the window are all less than or equal to n/4, move the left pointer to shrink the window and update the minimum length.

What is the best approach for Replace the Substring for Balanced String?

The optimal approach uses a sliding window with a frequency counter. Count how many times each character appears and track characters exceeding n/4. Expand a window and reduce counts for characters inside the window until the remaining string becomes balanced. This produces an O(n) time solution with O(1) space.

Is Replace the Substring for Balanced String asked at Google/Amazon/Meta?

Replace the Substring for Balanced String appears in many company-tagged interview preparation lists for large tech companies. Variants of sliding window string balancing problems are commonly asked in interviews at companies like Amazon, Google, and Meta because they test frequency counting and window optimization.

What data structure is used in Replace the Substring for Balanced String?

The solution mainly uses a frequency map or fixed-size array to count characters. Combined with two pointers forming a sliding window, it efficiently tracks how many characters remain outside the window and whether the balance condition is satisfied.

What is the time complexity of Replace the Substring for Balanced String?

The optimal sliding window solution runs in O(n) time because each pointer moves across the string at most once. The space complexity is O(1) since only four character counts (Q, W, E, R) are tracked regardless of input size.

Replace the Substring for Balanced String solution and explanation

The problem

Approach overview

Approach 1: Sliding Window Approach

Approach 2: Two-Pointer Technique

Approach 3: Counting + Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Replace the Substring for Balanced String solution and explanation

The problem

Approach overview

Approach 1: Sliding Window Approach

Approach 2: Two-Pointer Technique

Approach 3: Counting + Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems