Expressive Words

This approach involves pre-processing the main string s and each word in the words array into a run-length encoded (RLE) format. A run-length encoding represents a string as a list of pairs, where each pair contains a character and its consecutive count. For example, "heeellooo" becomes [('h', 1), ('e', 3), ('l', 2), ('o', 3)]. After encoding, we compare the RLE of each word with the RLE of s to check for the stretchy conditions.

• Define a helper class or structure, say RLE, to store the run-length encoded representation of a string. This structure would contain the compressed character sequence (e.g., as a string) and a list of counts for each character group.
• Implement a constructor or a function that takes a string and populates the RLE structure by iterating through the string and counting consecutive identical characters.
• In the main function expressiveWords, first create an RLE object for the input string s.
• Initialize a counter for stretchy words to zero.
• Iterate through each word in the words array.
• For each word, create its RLE representation.
• Compare the RLE of the word with the RLE of s:
  • First, check if their compressed character sequences are identical. If not, the word is not stretchy.
  • If the sequences match, iterate through the counts. For each corresponding pair of groups with counts count_w (from word) and count_s (from s):
    • The word is not stretchy if count_w > count_s.
    • The word is also not stretchy if count_s < 3 and count_w is not equal to count_s.
  • If all groups satisfy these conditions, the word is stretchy.
• Increment the counter for each stretchy word found.
• Return the total count.

The core idea is to abstract away the string traversal into a structured comparison. We first create a helper function or class to convert a string into its RLE representation. For the string s, this is done only once. Then, for each word in the input array, we also generate its RLE. The check for a word being 'stretchy' is then reduced to comparing these two RLE structures.

The comparison involves two main checks:

1. The compressed character sequences must be identical. This means the RLEs must have the same number of groups, and the character for each group must match in sequence.
2. For each corresponding group, the counts must satisfy the stretchy condition. Let count_s be the count from s's RLE and count_w from the word's RLE. The conditions are: count_w <= count_s, and if count_s < 3, then count_w must be exactly equal to count_s (no stretching is allowed if the final group size is less than 3).

If a word satisfies both conditions for all its character groups, it's counted as stretchy.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int expressiveWords(String s, String[] words) {
        RLE rleS = new RLE(s);
        int ans = 0;
        for (String word : words) {
            RLE rleWord = new RLE(word);
            if (!rleS.key.equals(rleWord.key)) {
                continue;
            }
            boolean stretchy = true;
            for (int i = 0; i < rleS.counts.size(); ++i) {
                int countS = rleS.counts.get(i);
                int countWord = rleWord.counts.get(i);
                if (countWord > countS || (countS < 3 && countWord != countS)) {
                    stretchy = false;
                    break;
                }
            }
            if (stretchy) {
                ans++;
            }
        }
        return ans;
    }
}

class RLE {
    String key;
    List<Integer> counts;

    public RLE(String s) {
        StringBuilder keyBuilder = new StringBuilder();
        counts = new ArrayList<>();
        if (s == null || s.length() == 0) {
            key = "";
            return;
        }
        
        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            int j = i;
            while (j < s.length() && s.charAt(j) == c) {
                j++;
            }
            keyBuilder.append(c);
            counts.add(j - i);
            i = j;
        }
        key = keyBuilder.toString();
    }
}