algoadvance

Leetcode 809. Expressive Words

Problem Statement

We are given a string S and a list of strings words. We want to determine how many words in the list can be considered “stretchy.” A word is stretchy if it can be made to match S by adding some number of the same character to every group of consecutive characters in S.

Formally, we can achieve a stretchy word by extending each group of consecutive characters of a word W such that each group W_i can be extended to match group S_i in S, under the conditions:

  1. If the length of S_i is 3 or more, we can extend W_i to any length equal to or larger than the length of S_i.
  2. If the length of S_i is exactly 2, W_i has to match S_i exactly (i.e., len(W_i) == len(S_i)).
  3. If the length of S_i is exactly 1.

Return the number of words in words that are stretchy.

Clarifying Questions

  1. Input Limits:
    • Is the length of S and words in words constrained in any way?
    • Are all strings guaranteed to be non-empty and consist of only lowercase English letters?
  2. Output:
    • Should the result be an integer representing the number of stretchy words?

Strategy

  1. Identify Groups:
    • Define a helper function split_to_groups to split any string into groups of consecutive characters along with their counts.
  2. Check Stretchy Compatibility:
    • Define a helper function is_stretchy to compare the groups from S with groups from a word in words using the given stretching rules.
  3. Main Function:
    • Iterate over each word in words, split S and the current word into groups, check if the word is stretchy using the is_stretchy function and count the number of stretchy words.

Code

import java.util.*;

public class ExpressiveWords {

    public static int expressiveWords(String S, String[] words) {
        int count = 0;
        
        List<Group> sGroups = split_to_groups(S);
        
        for (String word : words) {
            List<Group> wGroups = split_to_groups(word);
            if (is_stretchy(sGroups, wGroups)) {
                count++;
            }
        }
        
        return count;
    }

    private static List<Group> split_to_groups(String str) {
        List<Group> groups = new ArrayList<>();
        int i = 0;
        int len = str.length();
        
        while (i < len) {
            char c = str.charAt(i);
            int start = i;
            while (i < len && str.charAt(i) == c) {
                i++;
            }
            groups.add(new Group(c, i - start));
        }
        return groups;
    }

    private static boolean is_stretchy(List<Group> sGroups, List<Group> wGroups) {
        int sLen = sGroups.size();
        int wLen = wGroups.size();
        
        if (sLen != wLen) return false;
        
        for (int i = 0; i < sLen; i++) {
            Group sGroup = sGroups.get(i);
            Group wGroup = wGroups.get(i);
            
            if (sGroup.character != wGroup.character) return false;
            if (sGroup.count < wGroup.count) return false;
            if (sGroup.count > wGroup.count && sGroup.count < 3) return false;
        }
        
        return true;
    }
    
    private static class Group {
        char character;
        int count;
        
        public Group(char character, int count) {
            this.character = character;
            this.count = count;
        }
    }

    public static void main(String[] args) {
        String S = "heeellooo";
        String[] words = {"hello", "hi", "helo"};
        System.out.println(expressiveWords(S, words));  // Output: 1
    }
}

Time Complexity

The overall time complexity considering all words is O(m * w * k), where w is the number of words.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI