A master gemologist has a collection of rare gemstones arranged in a single row, represented by a string s. Each lowercase English letter in s represents a specific variety of gemstone. The gemologist wants to split the collection into two non-empty segments—a left exhibit and a right exhibit—to display in two separate halls. For the exhibition to feel balanced, the number of distinct gemstone varieties in the left exhibit must be exactly equal to the number of distinct gemstone varieties in the right exhibit. Return the number of valid split positions that achieve this balance.
Explanation: There are 4 possible ways to split the string "xyxxz" into two non-empty parts: - "x" and "yxxz": Left has 1 unique gemstone ('x'), right has 3 ('x', 'y', 'z'). Unbalanced. - "xy" and "xxz": Left has 2 unique gemstones ('x', 'y'), right has 2 ('x', 'z'). Balanced. - "xyx" and "xz": Left has 2 unique gemstones ('x', 'y'), right has 2 ('x', 'z'). Balanced. - "xyxx" and "z": Left has 2 unique gemstones ('x', 'y'), right has 1 ('z'). Unbalanced. Thus, there are 2 valid splits.
Explanation: There are 3 possible ways to split "aaaa": - "a" and "aaa": Both sides have 1 unique gemstone ('a'). Balanced. - "aa" and "aa": Both sides have 1 unique gemstone ('a'). Balanced. - "aaa" and "a": Both sides have 1 unique gemstone ('a'). Balanced. Thus, all 3 splits are balanced.
Master coding challenges related to Strings and solve the Balanced Gemstone Exhibits problem optimally.
No dry run loaded.
🚀 Practice this problem
Run code, get AI hints & track streak