All K Substrings - Generate All Substrings of Exactly Length K
Question Details
Problem
Given a string s and an integer k,
return all unique substrings of exactly length k, sorted lexicographically.
python
def all_k_substrings(s: str, k: int) -> List[str]:
...
Example:
**Input**: s="abcabc", k=3
Output: ["abc", "bca", "cab"]
# Sliding window gives: "abc","bca","cab","abc" -> unique sorted
**Input**: s="aaaa", k=2
Output: ["aa"]
**Input**: s="ab", k=5
Output: [] # k > len(s)
Approach
Slide a window of size k across s and collect all substrings into a set, then sort. Time O(n*k) for hashing, O(m log m * k) for sorting where m = number of unique substrings.
Follow-ups
- How would you use a rolling hash to reduce per-window work to O(1)?
- If
kis very large and the string has many repeats, what is the maximum number of unique substrings? - Extend:
return each unique substring along with its frequency (count of occurrences).
4. How does a suffix array solve this problem and what is its time complexity?
Full Details
Problem
Given a string s and an integer k,
return all unique substrings of exactly length k, sorted lexicographically.
python
def all_k_substrings(s: str, k: int) -> List[str]:
...
Example:
**Input**: s="abcabc", k=3
Output: ["abc", "bca", "cab"]
# Sliding window gives: "abc","bca","cab","abc" -> unique sorted
**Input**: s="aaaa", k=2
Output: ["aa"]
**Input**: s="ab", k=5
Output: [] # k > len(s)
Approach
Slide a window of size k across s and collect all substrings into a set, then sort. Time O(n*k) for hashing, O(m log m * k) for sorting where m = number of unique substrings.
Follow-ups
- How would you use a rolling hash to reduce per-window work to O(1)?
- If
kis very large and the string has many repeats, what is the maximum number of unique substrings? - Extend:
return each unique substring along with its frequency (count of occurrences).
4. How does a suffix array solve this problem and what is its time complexity?
About This Question
This is a reported interview question from a grammarly interview during the phone round.
It covers the following topics: Strings, Sliding Window, Phone, Coding, Arrays, Onsite .