Sometimes people repeat letters to represent extra feeling. For example:


	"hello" -&gt; "heeellooo"
	"hi" -&gt; "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" -&gt; "lllll" to get "helllllooo". If s = "helllllooo", then the query word "hello" would be stretchy because of these two extension operations: query = "hello" -&gt; "hellooo" -&gt; "helllllooo" = s.


Return the number of query strings that are stretchy.

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= s.length, words.length &lt;= 100
	1 &lt;= words[i].length &lt;= 100
	s and words[i] consist of lowercase letters.


class Solution:
    def expressiveWords(self, s: str, words: List[str]) -> int:
        # edge cases
        if len(s) == 0 and len(words) != 0:
            return False
        if len(words) == 0 and len(s) != 0:
            return False
        if len(s) == 0 and len(words) == 0:
            return True
     
        # helper function, compressing string and extract counts
        def compressor(s_word):
            init_string =[s_word[0]]
            array = []
            start = 0
            for i,c in enumerate(s_word):
                if c == init_string[-1]:
                    continue
                array.append(i-start)
                start = i
                init_string += c  
            array.append(i-start+1)    
            return init_string,array

        res = len(words)
        s_split, s_array = compressor(s)
        for word in words:
            word_split = ['']
            word_array = []
            word_split,word_array = compressor(word)
            if s_split == word_split:
                for num_s,num_word in zip(s_array,word_array):
                    if num_s != num_word and num_s < 3 or num_word > num_s:
                        res -= 1
                        break
            else:
                res -= 1
        return res
class Solution {
    private String getFreqString(String s) {
        int len = s.length();
        StringBuilder freqString = new StringBuilder();
        int currFreq = 1;
        char prevChar = s.charAt(0);
        freqString.append(s.charAt(0));
        for(int i = 1; i<len; i++) {
            if(s.charAt(i) == prevChar) {
                currFreq++;
            } else {
                freqString.append(currFreq);
                freqString.append(s.charAt(i));
                currFreq = 1;
            }
            prevChar = s.charAt(i);
        }
        
        if(currFreq>0) {
            freqString.append(currFreq);
        }
        
        return freqString.toString();
    }
    
    private boolean isGreaterButLessThanThree(char sChar, char wChar) {        
        return sChar > wChar && sChar < '3';
    }
    
    private boolean isStretchy(String s, String word) {    
        int sLen = s.length();
        int wordLen = word.length();
        
        if(sLen != wordLen) {
            return false;
        }
        
        for(int i = 0; i<sLen; i++) {
            char sChar = s.charAt(i);
            char wChar = word.charAt(i);
            if(i%2 != 0) {       
                if(sChar < wChar) {
                    return false;
                } if(isGreaterButLessThanThree(sChar, wChar)) {
                    return false;
                }
                
            } else if(sChar != wChar){
                    return false;
            }
        }
        
        return true;
    }
    
    public int expressiveWords(String s, String[] words) {
        int wordLen = words.length;
        if(wordLen < 1 || s.length() < 1) {
            return 0;
        }
        
        int stretchyWords = 0;
        String freqStringS = getFreqString(s);
        for(String word: words) {
            String freqStringWord = getFreqString(word); 
            if(isStretchy(freqStringS, freqStringWord)) {
                stretchyWords++;
            }
            
        }  
        return stretchyWords;
    }
}
class Solution {
public:
    
    // Basically get the length of a repeated sequence starting at pointer p. 
    int getRepeatedLen(string& s, int p) {
        int res = 0; 
        char c = s[p]; 
        while(p < s.size() && s[p] == c) {
            res++;
            p++;
        }
        return res; 
    }
    
    // Check if a word t is stretchy. i.e. can we turn word t into word s? 
    bool isStretchy(string& s, string& t, unordered_set<char>& sMap) {
        if(s == t) return true; 
        if(s.size() < t.size()) return false; // If t is bigger than the original string, return false since we can't take away characters. 
        int p1 = 0; // The first pointer will point to a char in our original string. 
        int p2 = 0; // The second pointer will point to a char in the word we want to stretch. 
        
        // Loop though the target string since we know it was to be either the same length or longer. i.e. "heeellooo" is longer than "hello". 
        while(p1 < s.size()) {
            if(!sMap.count(t[p2])) return false; // If we find a char in the word we want to stretch that's not even in our original string, we return false since we cannot remove chars. 
            int want = getRepeatedLen(s,p1); // For every new char we encounter we check how many are in the orignal string. 
            int have = getRepeatedLen(t,p2); 
            if( have > want) return false;  // Remember can't delete chars. 
            int needToAdd = want - have; 
            if(want != have && needToAdd + have < 3) return false; // If we need to add some chars, we have to also check if the new group size that we create follows our rules of being greater or equal to 3. 
            p1 += want; // We don't want to repeat a char again. 
            p2 += have; // Same as above but for the other word. 
        }
        return true; 
    }
    
    int expressiveWords(string s, vector<string>& words) {
        int res = 0; 
        unordered_set<char> sMap(s.begin(),s.end()); // Useful to know what characters exits in the first place. 
        // Basically loop through every word in the vector and check if it is stretchy. 
        for(string& w : words) {
            if(isStretchy(s,w,sMap)) res++; 
        }
        return res;
    }
};
/**
 * @param {string} s
 * @param {string[]} words
 * @return {number}
 */
var expressiveWords = function(s, words) {
    let arr = [];
    let curr = 0
    while(curr < s.length){
        let count = 1
        while(s[curr] === s[curr+1]){
            count++;
            curr++
        }
        arr.push([s[curr] , count]);
        curr++
    }
    let ans = 0
    for(let charArr of words){
        let idx = 0;
        let i = 0;
        let flag = true;
        if(charArr.length > s.length)continue

        while( i < charArr.length ){
            let count = 1
            while(charArr[i] === charArr[i+1]){
                i++;
                count++
            }
            if(arr[idx][0] !== charArr[i] || arr[idx][1] < count || (arr[idx][1] <3 && arr[idx][1] !== count) ){
                flag = false;
                break
            }
            idx++;
            i++

        }
        if(idx !== arr.length)flag = false
        if(flag)ans++
    }
    return ans
};
Expressive Words