Posts Group Shifted Strings
Post
Cancel

Group Shifted Strings

PROBLEM DESCRIPTION

Given a string s and an integer k, return the number of substrings in s of length k with no repeated characters.

leetcode

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();

    }


}
This post is licensed under CC BY 4.0 by the author.