# Group Shifted Strings Leetcode Solution

Difficulty Level Medium
WixViews 90

## Problem Statement

Group Shifted Strings Leetcode Solution – We can shift a string by shifting each of its letters to its successive letter.

• For example, `"abc"` can be shifted to be `"bcd"`.

We can keep shifting the string to form a sequence.

• For example, we can keep shifting `"abc"` to form the sequence: `"abc" -> "bcd" -> ... -> "xyz"`.

Given an array of strings `strings`, group all `strings[i]` that belong to the same shifting sequence. You may return the answer in any order.

Example 1:

Input:

``` strings = ["abc","bcd","acef","xyz","az","ba","a","z"]
```

Output:

``` [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]
```

Example 2:

Input:

``` strings = ["a"]
```

Output:

``` [["a"]]
```

Constraints:

• `1 <= strings.length <= 200`
• `1 <= strings[i].length <= 50`
• `strings[i]` consists of lowercase English letters.

## Approach

### Idea:

1. The basic idea of this problem is to set a key for each string
2. how do we set a key for any string?
3. we can say that if 2 strings belong to the same group then distance b/w adjacent characters in both remains the same
4. for example bc and xyz.
5. if s[i] – s[i – 1] is negative, we need to do (dis+26)%26 to it to make it positive and give the correct result
6. we make an unordered map <string, vector<string> >    we store the string corresponding to the key in a hashmap. ## Code

### C++ Program of  Group Shifted Strings

```class Solution {
public:
vector<vector<string>> groupStrings(vector<string>& strings) {

unordered_map<string,vector<string> > mp;

for(int i=0;i<strings.size();i++)
{
string key="-";
string s=strings[i];

for(int j=1;j<s.length();j++)
{
int dis=(s[j]-s[j-1]+26)%26;
key.append(to_string(dis));
key+='-';
}
mp[key].push_back(s);
}

vector<vector<string> > ans;
for(auto itr:mp)
{
ans.push_back(itr.second);
}
return ans;
}
};```

### Java  Program of  Group Shifted Strings

```class Solution {
public List<List<String>> groupStrings(String[] strings) {
Map<String,List<String>> mp = new HashMap<>();
for(int i=0;i<strings.length;i++)
{
String s=strings[i];
StringBuilder key  = new StringBuilder();
key.append("-");
for(int j = 1; j < s.length();j++)
{
int dis= (s.charAt(j) - s.charAt(j-1) + 26) % 26;
// in case [0,1,11] [0,11,1], so i add "." to key.
key.append(Integer.toString(dis));
key.append("-");

}
String k = key.toString();
if(!mp.containsKey(k)){
List<String> value = new ArrayList<>();
mp.put(k,value);
}
}
List<List<String>> ans = new ArrayList<>();
for(String key: mp.keySet()){
}
return ans;
}
}```

## Complexity Analysis for Group Shifted Strings Leetcode Solution

### Time Complexity

The time complexity of the above code is O(n*m)  where n is the size of the strings array and m is the   length of  string whose length is maximum in the array

### Space Complexity

The space complexity of the above code is O(n) because we are using a hash map to store the groups.

Translate »