Reference: OA
Difficulty: Medium

Problem

Given a string s and an int k, return all unique substrings of s of size k with k distinct characters.

Note:

  • The input string consists of only lowercase English letters [a-z].
  • 0 ≤ k ≤ 26

Example:

1
2
3
4
5
6
7
8
Input: s = "abcabc", k = 3
Output: ["abc", "bca", "cab"]

Input: s = "abacab", k = 3
Output: ["bac", "cab"]

Input: s = "awaglknagawunagwkwagl", k = 4
Output: ["wagl", "aglk", "glkn", "lkna", "knag", "gawu", "awun", "wuna", "unag", "nagw", "agwk", "kwag"]

Analysis

Playground: https://leetcode.com/playground/VsNDKQoK

1
2
3
4
5
6
7
8
9
10
11
public static void main(String[] args) {
String s1 = "abcabc"; int k1 = 3;
String s2 = "abacab"; int k2 = 3;
String s3 = "awaglknagawunagwkwagl"; int k3 = 4;
System.out.println(kSubstring1(s1, k1));
// Expected: ["abc", "bca", "cab"]
System.out.println(kSubstring1(s2, k2));
// Expected: ["bac", "cab"]
System.out.println(kSubstring1(s3, k3));
// Expected: ["wagl", "aglk", "glkn", "lkna", "knag", "gawu", "awun", "wuna", "unag", "nagw", "agwk", "kwag"]
}

Brute-Force

For each possible substrings, check if it is distinct.

Note: Strings in result are distinct too.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static List<String> kSubstring1(String s, int k) {
int n = s.length();
Set<String> result = new HashSet<>();
for (int i = 0; i + k <= n; ++i) {
String sub = s.substring(i, i + k);
if (isDistinct(sub)) {
result.add(sub);
}
}
return new ArrayList<>(result);
}

private static boolean isDistinct(String s) {
// Use hash set
Set<Character> set = new HashSet<>();
for (char ch : s.toCharArray()) {
set.add(ch);
}
return set.size() == s.length();
}

Time: $O(kN)$ where $N$ is the length of the string.
Space: $O(kN)$ since we need to store the result.

Sliding Window

Consider the follow examples for the sliding window to see why it works.

1
2
3
"abc"
"aba"
"abb"

start and end denote the range of the window. Particularly, end is the cursor that from 0 to n - 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static List<String> kSubstring2(String s, int k) {
int n = s.length();
Set<Character> window = new HashSet<>();
Set<String> result = new HashSet<>();
for (int start = 0, end = 0; end < n; ++end) {
char ch = s.charAt(end);
// duplicate: remove all elements that is before the existing element (inclusive)
while (window.contains(ch)) {
window.remove(s.charAt(start));
++start; // update the lower bound of the sliding window
}
window.add(ch);
// when size == k
if (window.size() == k) { // guarantee no duplicates
result.add(s.substring(start, end + 1)); // added
window.remove(s.charAt(start));
++start; // guarantee the size is not larger than k
}
}
return new ArrayList<>(result);
}

Time: $O(kN)$
Space: $O(kN)$


Comment