PROBLEM DESCRIPTION
Given a string s and an integer k, return the number of substrings in s of length k with no repeated characters.
SOLUTION
- We find how many shifts it would take if we had to change the first character to ‘a’
- We shift all the other character with the same amount
- We use this new string as a key in HashMap. This will help in grouping string which form the same shifted string
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
public List<List<String>> groupStrings(String[] strings) {
int n = strings.length;
// For all strings in the same kind, if we shift is in a way that the first character is a, that can be used as a unique key
// The corresponding value will be the actual string to be used in the answer
// For example:
// [abc, bcd, xyz] -> all the string belong to the same group
// abc -> can be changed to abc with 0 shift
// bcd -> can be changed to abc with 1 shift
// xyz -> can be changed to abc with (int) x-'a' shifts
// so, we can use 'abc' as the key to group them together
Map<String, List<String>> map = new HashMap<>();
// all each string
for(int i=0; i<n; i++){
// get the current string
String current = strings[i];
// calculate the string which is formed after shifting them such that the first character should become 0
String hashKey = calculateHash(current);
// if that key is not present, new a new list for this unique key
if(!map.containsKey(hashKey)){
map.put(hashKey, new ArrayList<String>());
}
// append the current string to the key
map.get(hashKey).add(current);
}
// go through all the values in the hashmap and create a List<List<String>> for final result to be returned
List<List<String>> ans = new ArrayList<>();
for(List<String> list: map.values()){
ans.add(list);
}
return ans;
}
public String calculateHash(String s){
// how many shifts are needed to change the first character to 'a'?
int shift = s.charAt(0) - 'a';
// the string which will be formed if we shift all characters by the number of times calculated above
StringBuffer sb = new StringBuffer();
// find the next character after shifting
for(int i=0; i<s.length(); i++){
// get the current character
char ch = s.charAt(i);
// get the character it will become after shifting
// tricky test case: ["az","ba"] -> both belong to the same group
char updatedCh = (char)((ch - shift + 26)%26);
// append it to the updated string
sb.append(updatedCh);
}
return sb.toString();
}
}