Problem Description

This is a character matching task where we modify input words to match a given form. The modification consists of expanding groups of similar characters to a size of 3 or greater while keeping the order of characters.

For instance, given a string "heeellooo", we are tasked to identify other words which can be modified to match it. Taking, "hello" -> "heeello" (by extending 'e') -> "heeellooo" (by extending the 'o'). This is possible because the sequence of characters is the same and we can extend the groups "e" and "o" from "hello" to match "heeellooo".

However, the word "helo" cannot be made to match "heeellooo" because the sequence character in the word "helo" ('h','e','l','o') does not match the sequence in "heeellooo" ('h','e','e','e','l','l','o','o','o').

The task is to find and count the number of "stretchy" words in the list of words.

Working Example

For example, given the string S = "heeellooo" and the list of words = ["hello", "hi", "helo"], we need to find the number of stretchy words in the input list.

1. We can extend "e" and "o" in the word "hello" to get "heeellooo". The "hello" is stretchy.

2. "hi" cannot be made stretchy to match the given string S because it does not contain the required characters in the correct order.

3. We can't extend "helo" to get "heeellooo" because the word "helo" does not have a second 'l' in the string.

Hence, the output will be 1 since we only have one stretchy word in the list.

Approach

The algorithm used here aims to iterate each of the given words, to check if a given word can be made stretchy to match the string S:

1. If the current character of the string S matched the character in the current word being processed, increment the index of the word.

2. If the current, previous, and next characters in string S are the same, skip the current character in string S.

3. If the current and previous characters in S are the same and optionally the next characters in S, skip the current character in S.

4. If the current character does not fall into any of the above conditions, return False.

After scanning the whole string S, check if the index of the word equals its length. This indicates if the word can be made stretchy or not.

Finally, count and return the number of stretchy words in the list.

Now, let's implement this solution in various programming languages.

Java Solution

1
2java
3class Solution {
4    public int expressiveWords(String S, String[] words) {
5        int count = 0;
6        for(String W : words) if(check(S, W)) count++;
7        return count;
8    }
9
10    public boolean check(String S, String W) {
11        int n = S.length(), m = W.length(), j = 0;
12        for (int i = 0; i < n; i++)
13            if (j < m && S.charAt(i) == W.charAt(j))
14                j++;
15            else if (i > 1 && S.charAt(i) == S.charAt(i-1) && S.charAt(i-1) == S.charAt(i-2))
16                ;
17            else if (0 < i && i+1 < n && S.charAt(i-1) == S.charAt(i) && S.charAt(i) == S.charAt(i+1))
18                ;
19            else
20                return false;
21        return j == m;
22    }
23}

Python Solution

1
2python
3class Solution:
4    def expressiveWords(self, S: str, words: List[str]) -> int:
5        def check(S, W):
6            i = 0
7            j = 0
8            for i in range(len(S)):
9                if j < len(W) and S[i] == W[j]: j += 1
10                elif i > 1 and S[i-2] == S[i-1] == S[i]: continue
11                elif 0 < i < len(S)-1 and S[i-1] == S[i] == S[i+1]: continue
12                else: return False
13            return j == len(W)
14                
15        return sum(check(S, W) for W in words)

Javascript Solution

1
2javascript
3var expressiveWords = function(S, words) {
4    let count = 0;
5    for (let W of words) count += check(S, W)? 1 : 0;
6    return count;
7};
8
9let check = (S, W) => {
10    let j = 0;
11        for (let i = 0; i < S.length; i++)
12            if (j < W.length && S.charAt(i) === W.charAt(j))
13                j++;
14            else if (i >= 2 && S.charAt(i - 2) == S.charAt(i - 1) && S.charAt(i - 1) == S.charAt(i))
15                continue;
16            else if (i >= 1 && i + 1 < S.length && S.charAt(i - 1) === S.charAt(i) && S.charAt(i) === S.charAt(i + 1))
17                continue;
18            else
19                return false;
20        return j === W.length;
21    };

C# Solution

1
2csharp
3public class Solution {
4    public int ExpressiveWords(string S, string[] words) {
5        int count = 0;
6        foreach (var word in words) 
7            if (check(S, word)) count++;
8        return count;
9    }
10  
11    private bool check(string S, string word) {
12        int j = 0;
13        for (int i = 0; i < S.Length; i++)
14            if (j < word.Length && S[i] == word[j])
15                j++;
16            else if (i >= 2 && S[i] == S[i-1] && S[i-1] == S[i-2])
17                continue;
18            else if (i >= 1 && i+1 < S.Length && S[i-1] == S[i] && S[i] == S[i+1])
19                continue;
20            else
21                return false;
22        return j == word.Length;
23    }
24}

C++ Solution

1
2c++
3class Solution{
4public:
5    int expressiveWords(string S, vector<string> &words)
6    {
7        int ans = 0;
8
9        for (const string &word : words)
10            ans += check(S, word);
11
12        return ans;
13    }
14
15private:
16    int check(string &s, string &w){
17        int n = s.size(), m = w.size(), j = 0;
18        
19        for(int i = 0; i < n; i++){
20            if(j < m && s[i] == w[j])
21                j++;
22            else if(i >= 2 && s[i] == s[i-1] && s[i-1] == s[i-2])
23                continue;
24            else if(i >= 1 && i+1 < n && s[i-1] == s[i] && s[i] == s[i+1])
25                continue;
26            else
27                return false;
28        }
29        
30        return j == m;
31    }
32};

Note

Here, we've implemented the check and counting the stretchy words directly in the loop for simplicity and less complexity. The key idea is to iterate over every word in the input to find stretchy words. For each word, we apply the condition checks mentioned above to find whether or not it is stretchy. If it is, we increment the count.The time complexity for the solution of this problem is O(NK), where N is the length of the input list of words, and K is the maximum length of a word in the input list.

The algorithm for this problem can potentially be optimized by applying dynamic programming. We could potentially split the word into "blocks" of continuous similar characters, and only compare these "blocks" instead of individual characters.

Additionally, the algorithm could potentially fail for certain edge cases, for instance, when the length of the input words is more significant as compared to the length of the given string 'S'. We would need to add checks to handle such cases, to ensure that the program returns the expected result consistently.

The solutions provided in different programming languages are relatively comparable in terms of performance. They all implement the same algorithm logic; hence, the execution speed would depend primarily on the inherent properties of the respective programming language.

Furthermore, it is crucial to note that the actual execution speed of these solutions may differ based on various factors such as compiler optimizations, hardware specifications, input size, etc.

In Python, we use list comprehension, which is more pythonic and efficient. JavaScript and Java have quite similar syntax, but JavaScript might perform slower due to its dynamic typing. C# and C++ are usually faster due to their direct access to memory and other low-level functionalities.

Overall, it is crucial to select a programming language and approach that suits the specific requirements and constraints of your project or use case.