What signals in a problem statement indicate the Prefix state / balance sub-pattern?

"equal number of 0s and 1s"; "every vowel appears an even number of times"; "more X than Y"; "longest" + a balance condition

Prefix state / balance (Prefix Sum Sub-pattern)

Q: What makes Prefix state / balance different from other sub-patterns?

You don't sum the original values — you sum (or XOR) a **recoded** version. And because the question asks for the longest, the map keeps the **first** index, never overwritten.

Recode each element so that "balanced" becomes "the same state as before": 0 → −1 and 1 → +1, or a bitmask of odd/even counts. Then the longest balanced range runs between the first and the latest time a state appears.

Signals in the problem statement

›
"equal number of 0s and 1s"
›
"every vowel appears an even number of times"
›
"more X than Y"
›
"longest" + a balance condition

What makes it different

You don't sum the original values — you sum (or XOR) a recoded version. And because the question asks for the longest, the map keeps the first index, never overwritten.

Questions

ordered from “learn the idea” to “recognise it without help”

1
Contiguous Array
Basic Anchor·LeetCode #525
WalkthroughMedium
2
Longest Substring Containing Vowels in Even Counts
Slight Variation·LeetCode #1371
WalkthroughMedium
3
Longest Well-Performing Interval
Tricky / Edge Case·LeetCode #1124
WalkthroughMedium

Template

first-index-template.cpp

// Longest subarray with equal numbers of 0s and 1s.
// Recode 0 -> -1, 1 -> +1: "balanced" now means "same running total as before".
int longestBalanced(vector<int>& nums) {
    unordered_map<int, int> first;  // running total -> FIRST index where it appeared
    first[0] = -1;                  // the empty prefix sits just before index 0
    int balance = 0, best = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        balance += nums[i] == 1 ? 1 : -1;
        auto it = first.find(balance);
        if (it != first.end()) best = max(best, i - it->second);
        else first[balance] = i;    // never overwrite: the earliest index gives the longest range
    }
    return best;
}

Remember this · Prefix Sum

Trigger

Range sums, "subarray sum equals K" (especially with negatives), equal counts, divisible by K.

Think

If I knew the total up to every index, would the answer become a difference of two totals?

Key question

Which earlier prefix value am I looking for when I stand at index i?

Exact sum + hash map Modulo / divisibility