# Expressive Words
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/expressive-words)
Canonical: https://scaleengineer.com/dsa/problems/expressive-words
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array, String
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco)
---
## Problem
Sometimes people repeat letters to represent extra feeling. For example:

* `"hello" -> "heeellooo"`
* `"hi" -> "hiiii"`

In these strings like `"heeellooo"`, we have groups of adjacent letters that are all the same: `"h"`, `"eee"`, `"ll"`, `"ooo"`.

You are given a string `s` and an array of query strings `words`. A query word is **stretchy** if it can be made to be equal to `s` by any number of applications of the following extension operation: choose a group consisting of characters `c`, and add some number of characters `c` to the group so that the size of the group is **three or more**.

* For example, starting with `"hello"`, we could do an extension on the group `"o"` to get `"hellooo"`, but we cannot get `"helloo"` since the group `"oo"` has a size less than three. Also, we could do another extension like `"ll" -> "lllll"` to get `"helllllooo"`. If `s = "helllllooo"`, then the query word `"hello"` would be **stretchy** because of these two extension operations: `query = "hello" -> "hellooo" -> "helllllooo" = s`.

Return _the number of query strings that are **stretchy**_.

**Example 1:**

**Input:** s = "heeellooo", words = ["hello", "hi", "helo"]
**Output:** 1
**Explanation:** 
We can extend "e" and "o" in the word "hello" to get "heeellooo".
We can't extend "helo" to get "heeellooo" because the group "ll" is not size 3 or more.

**Example 2:**

**Input:** s = "zzzzzyyyyy", words = ["zzyy","zy","zyy"]
**Output:** 3

**Constraints:**

* `1 <= s.length, words.length <= 100`
* `1 <= words[i].length <= 100`
* `s` and `words[i]` consist of lowercase letters.

# Approaches
## Run-Length Encoding
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.
**Time:** O(L_s + Σ L_w), where L_s is the length of `s` and L_w is the length of each word. This is because we iterate through each string once to create its RLE. If N is the number of words and L is the maximum string length, this is O(N * L). · **Space:** O(L), where L is the maximum length of the strings. In the worst case (e.g., a string with no consecutive characters), the RLE representation requires space proportional to the string's length.
**Pros:** The logic is cleanly separated into two phases: encoding and comparing, which can improve code readability and maintainability.; The RLE of the main string `s` is computed only once, which is efficient if the number of words is large.
**Cons:** Requires extra space to store the RLE representations, which can be O(L) for a string of length L.; The overhead of creating intermediate data structures (lists, custom objects) can make it slightly slower in practice than a direct in-place comparison, despite having the same time complexity class.
### Explanation
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.

```java
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();
    }
}
```
### Algorithm
- 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.

## Two Pointers
This approach avoids creating intermediate data structures by comparing the string `s` and each `word` directly using two pointers. We iterate through both strings simultaneously, identifying and comparing groups of identical characters on the fly. This method is more space-efficient as it operates in constant extra space for each comparison.
**Time:** O(L_s + Σ L_w), where L_s is the length of `s` and L_w is the length of each word. For each word, the `isStretchy` function performs a single pass over both `s` and the `word`. If N is the number of words and L is the maximum string length, this is O(N * L). · **Space:** O(1). The two-pointer approach uses only a few variables to keep track of indices, requiring constant extra space for each check.
**Pros:** Extremely space-efficient, using O(1) extra space for the comparison.; It's a direct and often faster approach in practice as it avoids the overhead of creating and managing intermediate data structures.
**Cons:** The logic within the checking loop is slightly more complex, as it combines traversal, group counting, and condition checking in a single pass.
### Explanation
Instead of pre-processing, this method performs a direct comparison. A helper function, `isStretchy(s, word)`, is used to determine if a single `word` is stretchy. This function uses a two-pointer technique. One pointer, `i`, traverses `s`, and another, `j`, traverses `word`.

The pointers advance through the strings together. At each position, we first ensure the characters `s[i]` and `word[j]` are the same. If they are, we count the length of the consecutive group of this character in both `s` (call it `count_s`) and `word` (call it `count_w`). This is done by looking ahead from the current pointers. 

We then apply the rules for a stretchy word on these counts: `count_w` cannot be greater than `count_s`. Furthermore, if `count_s` is less than 3, the group could not have been stretched, so `count_w` must be equal to `count_s`. If these conditions hold, we advance the main pointers `i` and `j` past the groups we just processed and continue the comparison. 

For a word to be stretchy, it's crucial that both pointers reach the end of their respective strings at the same time. This ensures that the compressed character sequences are identical.

```java
class Solution {
    public int expressiveWords(String s, String[] words) {
        int count = 0;
        for (String word : words) {
            if (isStretchy(s, word)) {
                count++;
            }
        }
        return count;
    }

    private boolean isStretchy(String s, String word) {
        int i = 0, j = 0;
        int n = s.length(), m = word.length();

        while (i < n && j < m) {
            if (s.charAt(i) != word.charAt(j)) {
                return false;
            }

            int i2 = i;
            while (i2 < n && s.charAt(i2) == s.charAt(i)) {
                i2++;
            }
            int countS = i2 - i;

            int j2 = j;
            while (j2 < m && word.charAt(j2) == word.charAt(j)) {
                j2++;
            }
            int countW = j2 - j;

            if (countW > countS || (countS < 3 && countW != countS)) {
                return false;
            }

            i = i2;
            j = j2;
        }

        return i == n && j == m;
    }
}
```
### Algorithm
- Initialize a counter for stretchy words to zero.
- Iterate through each `word` in the `words` array.
- For each `word`, call a helper function `isStretchy(s, word)` to check if it's a stretchy version of `s`.
- If `isStretchy` returns `true`, increment the counter.
- After checking all words, return the final count.

- **`isStretchy(s, word)` function algorithm:**
  - Initialize two pointers, `i` for `s` and `j` for `word`, both starting at 0.
  - Loop as long as both `i` and `j` are within the bounds of their respective strings.
  - Inside the loop, first check if `s.charAt(i)` equals `word.charAt(j)`. If not, return `false` immediately.
  - If characters match, count the length of the current group of identical characters in `s` starting from `i`. Let this be `count_s`.
  - Similarly, count the length of the group in `word` starting from `j`. Let this be `count_w`.
  - Apply the stretchy conditions: return `false` if `count_w > count_s` or if (`count_s < 3` and `count_w != count_s`).
  - Advance `i` by `count_s` and `j` by `count_w` to move to the next group.
  - After the loop, the word is stretchy only if both strings have been fully traversed. Return `true` if `i` is at the end of `s` AND `j` is at the end of `word`, otherwise return `false`.

# Solutions
### Java

```java
class Solution {
public
  int expressiveWords(String s, String[] words) {
    int ans = 0;
    for (String t : words) {
      if (check(s, t)) {
        ++ans;
      }
    }
    return ans;
  }
private
  boolean check(String s, String t) {
    int m = s.length(), n = t.length();
    if (n > m) {
      return false;
    }
    int i = 0, j = 0;
    while (i < m && j < n) {
      if (s.charAt(i) != t.charAt(j)) {
        return false;
      }
      int k = i;
      while (k < m && s.charAt(k) == s.charAt(i)) {
        ++k;
      }
      int c1 = k - i;
      i = k;
      k = j;
      while (k < n && t.charAt(k) == t.charAt(j)) {
        ++k;
      }
      int c2 = k - j;
      j = k;
      if (c1 < c2 || (c1 < 3 && c1 != c2)) {
        return false;
      }
    }
    return i == m && j == n;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int expressiveWords(string s, vector<string> &words) {
    auto check = [](string &s, string &t) -> int {
      int m = s.size(), n = t.size();
      if (n > m)
        return 0;
      int i = 0, j = 0;
      while (i < m && j < n) {
        if (s[i] != t[j])
          return 0;
        int k = i;
        while (k < m && s[k] == s[i])
          ++k;
        int c1 = k - i;
        i = k, k = j;
        while (k < n && t[k] == t[j])
          ++k;
        int c2 = k - j;
        j = k;
        if (c1 < c2 || (c1 < 3 && c1 != c2))
          return 0;
      }
      return i == m && j == n;
    };
    int ans = 0;
    for (string &t : words)
      ans += check(s, t);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def expressiveWords(self, s: str, words: List[str]) -> int: def check(s, t): m, n = len(s), len(t) if n > m: return False i = j = 0 while i < m and j < n: if s[i] != t[j]: return False k = i while k < m and s[k] == s[i]: k += 1 c1 = k - i i, k = k, j while k < n and t[k] == t[j]: k += 1 c2 = k - j j = k if c1 < c2 or (c1 < 3 and c1 != c2): return False return i == m and j == n return sum(check(s, t) for t in words)

```