Katkat
Back

Count Substrings with No Repeated Characters

NVIDIASoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Tests sliding window / two-pointer techniques to count all valid substrings without duplicate characters in linear time.

Count Substrings with No Repeated Characters

Given a string s consisting of lowercase English letters, return the total number of non-empty contiguous substrings that contain no repeated characters.

Substrings appearing at different start or end indices are considered distinct and should each be counted, even if their character sequences are identical.

Function Signature

def count_unique_substrings(s: str) -> int:
    pass

Constraints

  • 1 <= len(s) <= 100,000
  • s consists only of lowercase English letters ('a' - 'z').
  • The result can exceed standard 32-bit signed integer limits; use 64-bit integers where applicable.

Examples

Example 1

Input: s = "abc"
Output: 6
Explanation:
The valid non-empty substrings with no repeated characters are:
- Length 1: "a", "b", "c"
- Length 2: "ab", "bc"
- Length 3: "abc"
Total = 3 + 2 + 1 = 6.

Example 2

Input: s = "aba"
Output: 5
Explanation:
The valid non-empty substrings are:
- "a" (index 0..0)
- "b" (index 1..1)
- "a" (index 2..2)
- "ab" (index 0..1)
- "ba" (index 1..2)
Note that "aba" contains repeated 'a', so it is excluded. Total = 5.

Edge Cases to Consider

  • All identical characters (e.g., "aaaa" -> output should equal len(s)).
  • All unique characters (e.g., string of length n with all distinct characters -> n * (n + 1) // 2).
  • Single character string.

Hints

Hint 1

If you know the longest valid substring without duplicates that ends at index r, how many valid substrings end at index r?

Hint 2

Use a two-pointer sliding window where the right pointer expands the window and the left pointer advances past previous occurrences of duplicate characters.

Hint 3

Maintain the most recent index where each character appeared (using a fixed-size array or hash map) to jump the left pointer in O(1) time.

Follow-up questions

  • How would you adapt this solution if each character was allowed to appear at most k times instead of at most once?
  • How does the time and space complexity change if the alphabet is general Unicode instead of lowercase ASCII letters?
  • Could this be parallelized efficiently across multiple CPU threads or GPU blocks for very large texts?