Count Balanced Strings — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Strings and solve the Count Balanced Strings problem optimally.
O(N)O(1)Problem Description
Given an array of strings consisting solely of the characters 'x' and 'y', return the number of strings that satisfy both of the following conditions: (1) the count of 'x' characters equals the count of 'y' characters; (2) no two identical characters appear consecutively anywhere in the string. The empty string is considered to satisfy both conditions because it contains zero of each character and has no adjacent characters. Implement a function that receives the array and outputs the required count.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Count Balanced Strings"
WHY DOES IT MATTER?
Recognizing that two independent constraints collapse into a single structural property (alternating even‑length strings) lets you avoid heavy combinatorial logic and achieve linear performance, a skill frequently tested in interviews to assess pattern‑recognition ability.
OPTIMIZATION CHALLENGE
The key insight is that the balance condition is redundant once the alternating pattern and even length are verified, allowing you to drop the explicit count comparison and reduce the algorithm to a single pass with early exit.
REAL-WORLD CONNECTION
In network packet scheduling, alternating between two channels while keeping traffic balanced mirrors this problem—ensuring no channel is overloaded (balance) and avoiding consecutive bursts on the same channel (no identical adjacency).
When coding, first filter out odd‑length strings, then use a simple for‑loop that checks s[i]==s[i-1]; break immediately on a mismatch to save time, and remember that the empty string is a valid edge case.
COMPLEXITY AT A GLANCE
O(N)O(1)Core Theory — Why This Approach?
The problem reduces to recognizing two orthogonal constraints on binary strings over the alphabet {'x','y'}. The first constraint—equal numbers of 'x' and 'y'—implies the string length must be even, because each character contributes one to the total count. The second constraint—no two identical characters adjacent—forces the string into a strict alternating pattern. There are only two possible alternating templates for any even length: "xyxy…" or "yxyx…". Consequently, a string satisfies both conditions if and only if it is even‑length and matches one of these two templates. A naïve solution might count characters and then scan for adjacent duplicates for each string, which is O(L) per string but still optimal; however, many candidates over‑engineer the solution by attempting dynamic programming or combinatorial enumeration, which adds unnecessary overhead. The optimal paradigm is a single linear scan per string, checking adjacency while simultaneously tracking the net balance, allowing early termination when a violation is found. This yields overall linear time in the total input size and constant auxiliary space.
Interview Questions on This Problem
Q1How would you count the number of strings in an array that are both balanced (equal 'x' and 'y') and have no identical adjacent characters?
Iterate through each string, first reject odd‑length strings. Then scan the string once, ensuring s[i]!=s[i-1] for every i>0. If the scan finishes without a violation, the string is valid; increment a counter. The total time is O(N) where N is the sum of lengths.
Q2Why does an alternating pattern guarantee equal counts of 'x' and 'y' for even‑length strings?
In an alternating pattern each position alternates between the two characters. For an even length, the pattern repeats the pair exactly length/2 times, producing exactly length/2 occurrences of each character, thus satisfying the balance condition automatically.
Q3Can you extend this solution to a larger alphabet, say {'a','b','c'} with the same constraints (equal counts and no identical adjacency)? What changes?
With three symbols the alternating constraint alone no longer forces equal counts. The problem becomes a combinatorial counting task that typically requires DP or backtracking to enforce both global count equality and local adjacency constraints, leading to O(L·k) time where k is the alphabet size.
Examples
Input
["xy","xxyy","yx","xyx","yyxx"]
Output
2
Explanation: "xy" has 1 x and 1 y with no repeats → valid. "xxyy" has equal counts but contains "xx" → invalid. "yx" is valid. "xyx" has unequal counts → invalid. "yyxx" contains "yy" → invalid. Total valid strings = 2.
Input
["","x","y","xyxy","yxyx","xyyx"]
Output
3
Explanation: Empty string has 0 x and 0 y and no repeats → valid. "x" and "y" have unequal counts → invalid. "xyxy" and "yxyx" both have 2 x and 2 y with alternating characters → valid. "xyyx" contains "yy" → invalid. Total valid strings = 3.
Input
["xxxx","yyyy","xyxyxy","xyyxyx","yxxy"]
Output
1
Explanation: Only "xyxyxy" has equal numbers of x and y (3 each) and alternates characters. All other strings either have unequal counts or contain consecutive identical characters. Hence the answer is 1.
Constraints
- 1 <= strings.length <= 100000
- 0 <= strings[i].length <= 100000
- All characters in strings[i] are either 'x' or 'y'
- The total sum of lengths of all strings does not exceed 10^6
Optimal Approach & Strategy
First discard odd‑length strings, then perform a single pass checking s[i]!=s[i-1]; if the pass succeeds, the string is valid.
Brute Force Approach
Count 'x' and 'y' separately and then scan for adjacent duplicates for each string, rejecting any that fail either check.
Code Solutions
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim();
function parse(line){
if(line.length===0) return [];
return line.split(',').map(s=>s.trim());
}
function isBalanced(s){
let cntX=0,cntY=0;
for(let i=0;i<s.length;i++){
const ch=s[i];
if(ch==='x') cntX++; else if(ch==='y') cntY++; else return false;
}
if(cntX!==cntY) return false;
for(let i=1;i<s.length;i++) if(s[i]===s[i-1]) return false;
return true;
}
function countBalanced(arr){
let ans=0;
for(const s of arr){
if(isBalanced(s)) ans++;
}
return ans;
}
const arr=parse(input);
console.log(countBalanced(arr).toString());#include <bits/stdc++.h>
using namespace std;
bool isBalanced(const string& s){
int cntX=0,cntY=0;
for(char c: s){
if(c=='x') ++cntX; else if(c=='y') ++cntY; else return false; // invalid char
}
if(cntX!=cntY) return false;
for(size_t i=1;i<s.size();++i){
if(s[i]==s[i-1]) return false;
}
return true;
}
int countBalanced(const vector<string>& arr){
int ans=0;
for(const auto& s: arr){
if(isBalanced(s)) ++ans;
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string line;
if(!getline(cin,line)) return 0;
vector<string> arr;
string cur;
for(size_t i=0;i<=line.size();++i){
if(i==line.size()||line[i]==','){
size_t s=cur.find_first_not_of(' ');
size_t e=cur.find_last_not_of(' ');
if(s!=string::npos) arr.push_back(cur.substr(s,e-s+1));
else arr.push_back("");
cur.clear();
}else cur.push_back(line[i]);
}
cout<<countBalanced(arr);
return 0;
}import java.io.*;
import java.util.*;
public class Main {
private static boolean isBalanced(String s){
int cntX=0,cntY=0;
for(char c: s.toCharArray()){
if(c=='x') cntX++; else if(c=='y') cntY++; else return false;
}
if(cntX!=cntY) return false;
for(int i=1;i<s.length();i++) if(s.charAt(i)==s.charAt(i-1)) return false;
return true;
}
public static int countBalanced(List<String> arr){
int ans=0;
for(String s: arr){
if(isBalanced(s)) ans++;
}
return ans;
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
List<String> arr = new ArrayList<>();
if(line!=null && !line.isEmpty()){
for(String part: line.split(",")) arr.add(part.trim());
}
System.out.print(countBalanced(arr));
}
}import sys
def is_balanced(s: str) -> bool:
cnt_x = s.count('x')
cnt_y = s.count('y')
if cnt_x != cnt_y:
return False
for i in range(1, len(s)):
if s[i] == s[i-1]:
return False
return True
def count_balanced(arr):
return sum(1 for s in arr if is_balanced(s))
def parse(line: str):
if not line:
return []
return [part.strip() for part in line.split(',')]
if __name__ == "__main__":
line = sys.stdin.read().strip()
arr = parse(line)
print(count_balanced(arr))const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim();
function parse(line){
if(line.length===0) return [];
return line.split(',').map(s=>s.trim());
}
function isBalanced(s){
let cntX=0,cntY=0;
for(let i=0;i<s.length;i++){
const ch=s[i];
if(ch==='x') cntX++; else if(ch==='y') cntY++; else return false;
}
if(cntX!==cntY) return false;
for(let i=1;i<s.length;i++) if(s[i]===s[i-1]) return false;
return true;
}
function countBalanced(arr){
let ans=0;
for(const s of arr){
if(isBalanced(s)) ans++;
}
return ans;
}
const arr=parse(input);
console.log(countBalanced(arr).toString());Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.