Senior
Describe an algorithm for counting substrings with all unique characters.
sobes.tech AI
Answer from AI
To count the number of substrings with unique characters, the "sliding window" algorithm is usually used. The idea is to maintain a window in which all characters are unique and move it along the string, counting such substrings.
Main steps:
- Use two pointers —
leftandright, which define the boundaries of the window. - Use a data structure (for example, a map or array) to track encountered characters and their counts.
- Expand the window to the right, adding characters until all are unique.
- If a repeating character is encountered, move the left pointer to the right, decreasing character counts until the repeat disappears.
- At each step, you can count the number of unique substrings, for example, by adding
right - left + 1.
Example in Go:
func countUniqueSubstrings(s string) int {
freq := make(map[rune]int)
left, count := 0, 0
for right, ch := range s {
freq[ch]++
for freq[ch] > 1 {
freq[rune(s[left])]--
left++
}
count += right - left + 1
}
return count
}
Here, count is the total number of substrings with unique characters.