LeetCode 3340 - Check Balanced String

The problem gives us a string num that contains only numeric digits from '0' to '9'. We must determine whether the string is "balanced". A string is considered balanced when the sum of digits located at even indices is equal to the sum of digits located at odd indices.

leetcodeeasystring

LeetCode Problem 3340

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem gives us a string num that contains only numeric digits from '0' to '9'. We must determine whether the string is "balanced".

A string is considered balanced when the sum of digits located at even indices is equal to the sum of digits located at odd indices.

Indexing is zero-based, which means:

  • Index 0 is even
  • Index 1 is odd
  • Index 2 is even
  • Index 3 is odd
  • And so on

For example, in the string "1234":

  • Even indices are 0 and 2, digits are 1 and 3
  • Odd indices are 1 and 3, digits are 2 and 4

The sums become:

  • Even index sum = 1 + 3 = 4
  • Odd index sum = 2 + 4 = 6

Since the sums are different, the string is not balanced.

The input size is very small because the string length is at most 100. This means performance is not a major concern, and even straightforward approaches will run comfortably within limits. However, we still want to write a clean and efficient solution.

The problem guarantees that:

  • The string length is at least 2
  • Every character is a digit

Because of these guarantees, we do not need to validate input format or handle empty strings.

Some important edge cases include:

  • Strings where all digits are zero, such as "00"
  • Very short strings of length 2
  • Strings where only one side contributes significantly to the total
  • Odd-length strings, where the number of even-indexed digits differs from the number of odd-indexed digits

A correct implementation must handle all of these consistently.

Approaches

Brute Force Approach

A brute-force solution would explicitly build two separate collections:

  • One containing digits at even indices
  • One containing digits at odd indices

After constructing these collections, we could sum both lists separately and compare the totals.

This approach is correct because every digit is categorized exactly once according to its index parity. If the two computed sums are equal, the string is balanced.

However, this method uses unnecessary extra space because we do not actually need to store the digits. We only need the running totals.

Optimal Approach

The key observation is that we can compute both sums during a single traversal of the string.

As we iterate through each character:

  • Convert the character into an integer digit
  • If the index is even, add it to the even sum
  • Otherwise, add it to the odd sum

At the end, simply compare the two totals.

This works because the balance condition depends only on the final sums, not on the individual digits after processing.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Stores separate collections for even and odd digits
Optimal O(n) O(1) Computes sums directly during one traversal

Algorithm Walkthrough

  1. Initialize two variables:
  • even_sum = 0
  • odd_sum = 0

These variables will store the cumulative sums of digits at even and odd indices. 2. Traverse the string from left to right using both the index and character.

We need the index to determine whether the current position is even or odd. 3. Convert the current character into an integer digit.

Since the string contains only numeric characters, conversion is always valid. 4. Check the parity of the current index.

  • If index % 2 == 0, add the digit to even_sum
  • Otherwise, add the digit to odd_sum
  1. Continue until all characters have been processed.
  2. Compare the two sums.
  • Return True if they are equal
  • Return False otherwise

Why it works

The algorithm processes every digit exactly once and places its value into the correct sum based on index parity. Because every index is either even or odd, all digits are accounted for correctly. At the end of traversal, even_sum equals the sum of all digits at even indices, and odd_sum equals the sum of all digits at odd indices. Comparing these values directly determines whether the string is balanced.

Python Solution

class Solution:
    def isBalanced(self, num: str) -> bool:
        even_sum = 0
        odd_sum = 0

        for index, digit_char in enumerate(num):
            digit = int(digit_char)

            if index % 2 == 0:
                even_sum += digit
            else:
                odd_sum += digit

        return even_sum == odd_sum

The implementation begins by initializing two running totals, one for even indices and one for odd indices.

The enumerate function is used so that we can access both the current index and the digit character during iteration. Each character is converted into an integer using int().

The parity of the index determines which sum receives the digit. If the index is divisible by 2, the digit belongs to the even-index sum. Otherwise, it belongs to the odd-index sum.

After the loop finishes, the function compares the two totals and returns the result of that comparison directly.

Go Solution

func isBalanced(num string) bool {
    evenSum := 0
    oddSum := 0

    for i, ch := range num {
        digit := int(ch - '0')

        if i%2 == 0 {
            evenSum += digit
        } else {
            oddSum += digit
        }
    }

    return evenSum == oddSum
}

The Go implementation follows the same logic as the Python solution.

One important difference is character-to-integer conversion. In Go, characters are represented as rune values, so we convert a digit character into its numeric value using:

digit := int(ch - '0')

This works because digit characters are stored consecutively in the character encoding.

No special handling for empty strings or invalid characters is needed because the problem constraints guarantee valid input.

Worked Examples

Example 1

Input:

num = "1234"
Index Digit Even Sum Odd Sum
0 1 1 0
1 2 1 2
2 3 4 2
3 4 4 6

Final comparison:

4 != 6

Result:

false

Example 2

Input:

num = "24123"
Index Digit Even Sum Odd Sum
0 2 2 0
1 4 2 4
2 1 3 4
3 2 3 6
4 3 6 6

Final comparison:

6 == 6

Result:

true

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every digit is processed exactly once
Space O(1) Only a few integer variables are used

The algorithm performs a single pass through the string. Each iteration involves constant-time work: converting a digit and updating one sum. No additional data structures proportional to input size are allocated, so the space usage remains constant.

Test Cases

solution = Solution()

assert solution.isBalanced("1234") == False  # Provided example, unequal sums
assert solution.isBalanced("24123") == True  # Provided example, balanced

assert solution.isBalanced("00") == True  # Smallest valid balanced case
assert solution.isBalanced("11") == True  # Equal digits at both positions
assert solution.isBalanced("12") == False  # Smallest unbalanced case

assert solution.isBalanced("1212") == True  # Alternating equal sums
assert solution.isBalanced("1111") == True  # All digits same
assert solution.isBalanced("9999") == True  # Large equal digits

assert solution.isBalanced("12345") == False  # Odd length, unequal sums
assert solution.isBalanced("54321") == True  # Odd length, balanced

assert solution.isBalanced("1001") == False  # Uneven distribution
assert solution.isBalanced("1010") == True  # Balanced with zeros

assert solution.isBalanced("9876543210") == False  # Larger input
assert solution.isBalanced("000000") == True  # All zeros

print("All tests passed!")
Test Why
"1234" Verifies standard unbalanced case
"24123" Verifies standard balanced case
"00" Tests smallest balanced input
"11" Tests equal two-digit input
"12" Tests smallest unbalanced input
"1212" Tests alternating pattern
"1111" Tests repeated identical digits
"9999" Tests large digit values
"12345" Tests odd-length unbalanced string
"54321" Tests odd-length balanced string
"1001" Tests imbalance caused by zeros
"1010" Tests zeros mixed with nonzero digits
"9876543210" Tests larger multi-digit input
"000000" Tests all-zero input

Edge Cases

One important edge case is the smallest possible input size, such as "12". Since the string length can be as small as 2, the algorithm must correctly compare exactly one even-indexed digit and one odd-indexed digit. The implementation handles this naturally because the loop processes every character independently.

Another important case is strings containing only zeros, such as "000000". A buggy implementation might incorrectly assume nonzero digits are required for balance. In reality, both sums become zero, so the string is balanced. The running-sum approach correctly computes this.

Odd-length strings are also significant. For example, "54321" has more even-index positions than odd-index positions. Some implementations incorrectly assume both groups contain the same number of digits. The algorithm avoids this issue entirely because it only compares total sums, not counts.

A final edge case involves very repetitive inputs like "9999" or "111111". These cases ensure the implementation does not accidentally skip indices or mis-handle parity calculations. Since the algorithm explicitly checks index % 2, every position is categorized correctly.