## Algorithm

Problem Name: 809. Expressive Words

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

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int expressiveWords(string S, vector& words) {
int res = 0;
vectorletter;
vectorcount;
for(int i = 0, index = 0; i < S.size(); index++){
letter.push_back(S[i]);
count.push_back(1);
int j = i + 1;
while(j < S.size() && S[j] == S[i]) count[index]++, j++;
i = j;
}

for(auto s: words){
vectorv;
vectorc;
bool b = true;
int index = 0;
for(int i = 0; i < s.size(); index++){
v.push_back(s[i]);
c.push_back(1);
int j = i + 1;
while(j < s.size() && s[j] == s[i]) c[index]++, j++;
if(v[index] != letter[index] || (c[index] != count[index] && count[index] < 3) || c[index] > count[index]){
b = false;
break;
}
i = j;
}
if(b && index == count.size()) res++;
}
return res;
}
};

class Solution {
public:
int expressiveWords(string S, vector& words) {
int res = 0;
for (auto& x: words) {
if (isValid(x, S)) {
++res;
}
}
return res;
}

bool isValid(string& x, string& y) {
if (x.size() > y.size()) {
return false;
}

int i = 0, j = 0, m = x.size(), n = y.size();
while (i < m) {
if (x[i] != y[j]) {
return false;
}

int count1 = 1, count2 = 1;
while (i + 1 < m && x[i] == x[i + 1]) {
++i;
++count1;
}

while(j + 1 < n && y[j] == y[j + 1]) {
++j;
++count2;
}
++i;
++j;
if (count1 == count2 || (count1 < count2 && count2 >= 3)) {
continue;
} else {
return false;
}
}
return i == m && j == n;
}
};
``````
Copy The Code &

Input

cmd
s = "heeellooo", words = ["hello", "hi", "helo"]

Output

cmd
1

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int expressiveWords(String s, String[] words) {
return (int) Arrays.stream(words).filter(word -> isExpressive(s, word)).count();
}

private boolean isExpressive(String s, String word) {
int sIdx = 0;
int wordIdx = 0;
while (sIdx < s.length() && wordIdx < word.length()) {
if (s.charAt(sIdx) != word.charAt(wordIdx)) {
return false;
}
char c1 = s.charAt(sIdx);
int countC1 = 0;
while (sIdx < s.length() && s.charAt(sIdx) == c1) {
sIdx++;
countC1++;
}
char c2 = word.charAt(wordIdx);
int countC2 = 0;
while (wordIdx < word.length() && word.charAt(wordIdx) == c2) {
wordIdx++;
countC2++;
}
if (countC1 == countC2 || (countC1 > countC2 && countC1 >= 3)) {
continue;
}
return false;
}
return sIdx == s.length() && wordIdx == word.length();
}
}
``````
Copy The Code &

Input

cmd
s = "heeellooo", words = ["hello", "hi", "helo"]

Output

cmd
1

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def expressiveWords(self, S, words):
if not S: return 0
guide, i, j, res = [], 0, 0, 0
while i < len(S):
while j + 1 ``````
``` Copy The Code & Input x – + cmd s = "zzzzzyyyyy", words = ["zzyy","zy","zyy"] Output x – + cmd 3 ```
``` #4 Code Example with C# Programming Code - C# Programming using System.Collections.Generic; namespace LeetCode { public class _0809_ExpressiveWords { public int ExpressiveWords(string S, string[] words) { (var keys, var counts) = CountString(S); var result = 0; foreach (var word in words) { (var wordKeys, var wordCounts) = CountString(word); if (keys.Count != wordKeys.Count) continue; var continueNext = false; for (int i = 0; i < keys.Count; i++) { if (keys[i] != wordKeys[i] || counts[i] < wordCounts[i] || (counts[i] < 3 && counts[i] != wordCounts[i])) { continueNext = true; break; } } if (continueNext) continue; result++; } return result; } private (IList keys, IList counts) CountString(string str) { var keys = new List(); var counts = new List(); for (int i = 0; i < str.Length; i++) { var count = 1; while (i + 1 < str.Length && str[i] == str[i + 1]) { count++; i++; } keys.Add(str[i]); counts.Add(count); } return (keys, counts); } } } Copy The Code & Input x – + cmd s = "zzzzzyyyyy", words = ["zzyy","zy","zyy"] Output x – + cmd 3 Demonstration ```
``` #808 Leetcode Soup Servings Solution in C, C++, Java, JavaScript, Python, C# Leetcode #810 Leetcode Chalkboard XOR Game Solution in C, C++, Java, JavaScript, Python, C# Leetcode ```
``` ```