Check Balanced String

Difficulty: Easy | Acceptance: 82.60% | Paid: No Topics: String

You are given a string s consisting only of digits. A string is balanced if the sum of the digits in the first half of the string is equal to the sum of the digits in the second half of the string.

Return true if s is balanced, otherwise return false.

• Examples
• Constraints
• Two-Pass Summation
• Single Pass Two Pointers
• Single Pass Net Balance

Examples

Example 1

Input:

num = "1234"

Output:

false

Explanation: The sum of digits at even indices is 1 + 3 == 4, and the sum of digits at odd indices is 2 + 4 == 6.

Since 4 is not equal to 6, num is not balanced.

Example 2

Input:

num = "24123"

Output:

true

Explanation: The sum of digits at even indices is 2 + 1 + 3 == 6, and the sum of digits at odd indices is 4 + 2 == 6.

Since both are equal the num is balanced.

Constraints

2 <= s.length <= 100
s.length is even.
s consists of only digits.

Two-Pass Summation

Intuition We can simply iterate through the first half of the string to calculate the sum of those digits, then iterate through the second half to calculate the sum of the remaining digits. Finally, we compare the two sums.

Steps

• Calculate the midpoint of the string length.
• Iterate from the start to the midpoint, converting characters to integers and accumulating the sum in sum1.
• Iterate from the midpoint to the end, converting characters to integers and accumulating the sum in sum2.
• Return true if sum1 equals sum2, otherwise false.

class Solution:
    def isBalanced(self, s: str) -> bool:
        n = len(s)
        half = n // 2
        sum1 = 0
        for i in range(half):
            sum1 += int(s[i])
        
        sum2 = 0
        for i in range(half, n):
            sum2 += int(s[i])
            
        return sum1 == sum2

Complexity

• Time: O(n) where n is the length of the string. We iterate through the string exactly once (split into two loops).
• Space: O(1) as we only use a few integer variables for storage.
• Notes: This is the most straightforward approach but requires two separate loop structures.

Single Pass Two Pointers

Intuition Instead of calculating sums separately, we can iterate through both halves simultaneously using two pointers. One pointer starts at the beginning, and the other starts at the midpoint. We accumulate sums for both halves in a single loop.

Steps

• Initialize left pointer to 0 and right pointer to n / 2.
• Initialize sum1 and sum2 to 0.
• Loop while right is less than n.
• Add the digit at s[left] to sum1 and the digit at s[right] to sum2.
• Increment both left and right.
• Return true if sum1 equals sum2, otherwise false.

class Solution:
    def isBalanced(self, s: str) -> bool:
        n = len(s)
        half = n // 2
        sum1 = 0
        sum2 = 0
        
        for i in range(half):
            sum1 += int(s[i])
            sum2 += int(s[half + i])
            
        return sum1 == sum2

Complexity

• Time: O(n) where n is the length of the string. We iterate n/2 times, performing constant work each time.
• Space: O(1) as we only use a few integer variables.
• Notes: Slightly cleaner loop structure than the two-pass approach, but effectively the same performance.

Single Pass Net Balance

Intuition We can optimize space slightly (conceptually) by maintaining a single “balance” variable. We add digits from the first half to this balance and subtract digits from the second half. If the string is balanced, the final result will be zero.

Steps

• Initialize balance to 0.
• Iterate through the string with index i from 0 to n - 1.
• If i is in the first half (i < n / 2), add the digit value to balance.
• If i is in the second half (i >= n / 2), subtract the digit value from balance.
• Return true if balance is 0, otherwise false.

class Solution:
    def isBalanced(self, s: str) -> bool:
        n = len(s)
        half = n // 2
        balance = 0
        
        for i in range(n):
            digit = int(s[i])
            if i < half:
                balance += digit
            else:
                balance -= digit
                
        return balance == 0

Complexity

• Time: O(n) where n is the length of the string. We iterate through the string exactly once.
• Space: O(1) as we only use a single integer variable for the balance.
• Notes: This is the most elegant solution as it reduces the problem to a single accumulation check.