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)$