Prefix Sums on Strings: Balanced Substrings

Concepts: pyStringPrefixSum, pyBalancedSubstring, pyRecodePattern

Prefix sums are not limited to numeric arrays. Strings are arrays of characters, and you can precompute character frequency prefix arrays -- one per character -- to answer 'how many of character X appear between index i and j' in O(1). More powerfully, you can encode binary string properties (is this character a vowel or consonant? 0 or 1?) as a numeric prefix sum and use the hash map combo to find balanced substrings in O(n). This unlocks a whole family of string problems that naive approaches solve in O(n^2). Vowel Count Prefix Array Finding Balanced Substrings (Equal 0s and 1s) LeetCode 525: given a binary string, find the longest contiguous substring with equal numbers of 0s and 1s. The trick: recode 0 as -1. Now 'equal 0s and 1s' becomes 'sum equals 0.' Apply the prefix sum + hash map