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 arestretchy.

Examples

Example 1

1
2
3
4
5

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

1
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.

Solution

Method 1 – Two Pointers and Group Counting

Intuition

The key idea is to compare the groups of consecutive characters in both the target string s and each word. For a word to be “stretchy,” every group in the word must match the corresponding group in s by character, and the group in s must be either the same length as in the word, or at least 3 and not shorter than the word’s group.

Approach

  1. For each word in words:
    • Use two pointers to traverse s and the word simultaneously.
    • For each group of consecutive characters:
      • Count the length of the group in both s and the word.
      • If the characters differ, or the group in s is shorter than in the word, or the group in s is less than 3 and not equal in length to the word’s group, the word is not stretchy.
    • If both pointers reach the end, the word is stretchy.
  2. Count and return the number of stretchy words.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int expressiveWords(string s, vector<string>& words) {
        int ans = 0;
        for (auto& w : words) {
            int i = 0, j = 0, n = s.size(), m = w.size();
            bool ok = true;
            while (i < n && j < m) {
                if (s[i] != w[j]) { ok = false; break; }
                int ii = i, jj = j;
                while (ii < n && s[ii] == s[i]) ii++;
                while (jj < m && w[jj] == w[j]) jj++;
                int lenS = ii - i, lenW = jj - j;
                if (lenS < lenW) { ok = false; break; }
                if (lenS != lenW && lenS < 3) { ok = false; break; }
                i = ii; j = jj;
            }
            if (ok && i == n && j == m) ans++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func expressiveWords(s string, words []string) int {
    ans := 0
    for _, w := range words {
        i, j, n, m := 0, 0, len(s), len(w)
        ok := true
        for i < n && j < m {
            if s[i] != w[j] { ok = false; break }
            ii, jj := i, j
            for ii < n && s[ii] == s[i] { ii++ }
            for jj < m && w[jj] == w[j] { jj++ }
            lenS, lenW := ii-i, jj-j
            if lenS < lenW || (lenS != lenW && lenS < 3) { ok = false; break }
            i, j = ii, jj
        }
        if ok && i == n && j == m { ans++ }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int expressiveWords(String s, String[] words) {
        int ans = 0;
        for (String w : words) {
            int i = 0, j = 0, n = s.length(), m = w.length();
            boolean ok = true;
            while (i < n && j < m) {
                if (s.charAt(i) != w.charAt(j)) { ok = false; break; }
                int ii = i, jj = j;
                while (ii < n && s.charAt(ii) == s.charAt(i)) ii++;
                while (jj < m && w.charAt(jj) == w.charAt(j)) jj++;
                int lenS = ii - i, lenW = jj - j;
                if (lenS < lenW) { ok = false; break; }
                if (lenS != lenW && lenS < 3) { ok = false; break; }
                i = ii; j = jj;
            }
            if (ok && i == n && j == m) ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun expressiveWords(s: String, words: Array<String>): Int {
        var ans = 0
        for (w in words) {
            var i = 0; var j = 0; val n = s.length; val m = w.length
            var ok = true
            while (i < n && j < m) {
                if (s[i] != w[j]) { ok = false; break }
                var ii = i; var jj = j
                while (ii < n && s[ii] == s[i]) ii++
                while (jj < m && w[jj] == w[j]) jj++
                val lenS = ii - i; val lenW = jj - j
                if (lenS < lenW) { ok = false; break }
                if (lenS != lenW && lenS < 3) { ok = false; break }
                i = ii; j = jj
            }
            if (ok && i == n && j == m) ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def expressiveWords(self, s: str, words: list[str]) -> int:
        ans = 0
        for w in words:
            i = j = 0
            n, m = len(s), len(w)
            ok = True
            while i < n and j < m:
                if s[i] != w[j]:
                    ok = False
                    break
                ii, jj = i, j
                while ii < n and s[ii] == s[i]:
                    ii += 1
                while jj < m and w[jj] == w[j]:
                    jj += 1
                lenS, lenW = ii - i, jj - j
                if lenS < lenW or (lenS != lenW and lenS < 3):
                    ok = False
                    break
                i, j = ii, jj
            if ok and i == n and j == m:
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn expressive_words(s: String, words: Vec<String>) -> i32 {
        let mut ans = 0;
        for w in words {
            let (mut i, mut j, n, m) = (0, 0, s.len(), w.len());
            let (s_bytes, w_bytes) = (s.as_bytes(), w.as_bytes());
            let mut ok = true;
            while i < n && j < m {
                if s_bytes[i] != w_bytes[j] { ok = false; break; }
                let (mut ii, mut jj) = (i, j);
                while ii < n && s_bytes[ii] == s_bytes[i] { ii += 1; }
                while jj < m && w_bytes[jj] == w_bytes[j] { jj += 1; }
                let (len_s, len_w) = (ii - i, jj - j);
                if len_s < len_w || (len_s != len_w && len_s < 3) { ok = false; break; }
                i = ii; j = jj;
            }
            if ok && i == n && j == m { ans += 1; }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    expressiveWords(s: string, words: string[]): number {
        let ans = 0;
        for (const w of words) {
            let i = 0, j = 0, n = s.length, m = w.length;
            let ok = true;
            while (i < n && j < m) {
                if (s[i] !== w[j]) { ok = false; break; }
                let ii = i, jj = j;
                while (ii < n && s[ii] === s[i]) ii++;
                while (jj < m && w[jj] === w[j]) jj++;
                const lenS = ii - i, lenW = jj - j;
                if (lenS < lenW || (lenS !== lenW && lenS < 3)) { ok = false; break; }
                i = ii; j = jj;
            }
            if (ok && i === n && j === m) ans++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(N * K), where N is the number of words and K is the average length of the strings. Each word is compared to s in linear time.
  • 🧺 Space complexity: O(1), as only a constant amount of extra space is used for pointers and counters.