LeetCode 2157: Groups of Strings Solution

Master LeetCode problem 2157 (Groups of Strings), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2157. Groups of Strings

Hard

String Bit Manipulation Union Find

Problem Explanation

Explanation

To solve this problem, we can represent each string as a set of characters. We can then iterate through each pair of strings and check if they are connected based on the given operations. We can use a union-find data structure to group connected strings together. Finally, we calculate the number of groups and the size of the largest group.

Algorithm:
1. Create a map to store the index of each word.
2. Initialize a union-find data structure to group connected strings.
3. Iterate through each word:
  - Convert the word into a set of characters.
  - If the word is not in the map, add it to the map and assign it an index.
  - Iterate through each character in the word:
    - Generate all possible strings by adding, deleting, or replacing one character.
    - If the generated string is in the map, merge the indices of the current word and the generated string in the union-find data structure.
4. Calculate the number of groups and the size of the largest group by iterating through the union-find data structure.
5. Return the result.
Time Complexity:
- The time complexity of this approach is O(n * m^2), where n is the number of words and m is the maximum length of a word.
Space Complexity:
- The space complexity is O(n * m) to store indices and the union-find data structure.

Solution Code

class Solution {
    public int[] groupStrings(String[] words) {
        int n = words.length;
        Map<String, Integer> indexMap = new HashMap<>();
        UnionFind uf = new UnionFind(n);
        
        for (int i = 0; i < n; i++) {
            String word = words[i];
            indexMap.put(word, i);
            
            Set<String> set = new HashSet<>();
            set.add(word);
            
            for (int j = 0; j < word.length(); j++) {
                StringBuilder sb = new StringBuilder(word);
                char c = sb.charAt(j);
                
                sb.deleteCharAt(j);
                set.add(sb.toString());
                
                for (char newChar = 'a'; newChar <= 'z'; newChar++) {
                    if (newChar != c) {
                        sb.setCharAt(j, newChar);
                        set.add(sb.toString());
                    }
                }
            }
            
            for (String str : set) {
                if (indexMap.containsKey(str)) {
                    uf.union(i, indexMap.get(str));
                }
            }
        }
        
        int maxGroupSize = 0;
        int numGroups = 0;
        
        for (int i = 0; i < n; i++) {
            if (uf.find(i) == i) {
                numGroups++;
                maxGroupSize = Math.max(maxGroupSize, uf.size[i]);
            }
        }
        
        return new int[]{numGroups, maxGroupSize};
    }
    
    class UnionFind {
        int[] parent;
        int[] size;
        
        public UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            }
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2157 (Groups of Strings)?

This page provides optimized solutions for LeetCode problem 2157 (Groups of Strings) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2157 (Groups of Strings)?

The time complexity for LeetCode 2157 (Groups of Strings) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2157 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2157 in Java, C++, or Python.

Back to LeetCode Solutions