Expressive Words - Practice Coding Problems

Expressive Words - Problem

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

"hello" → "heeellooo"
"hi" → "hiiii"

In 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 equal to s by extending character groups to have 3 or more characters.

For example, starting with "hello", we could extend the group "o" to get "hellooo", but we cannot get "helloo" since the group "oo" has size less than 3. We could also extend "ll" → "lllll" to get "helllllooo".

Return the number of query strings that are stretchy.

Input & Output

Example 1 — Basic Stretching

$ Input: s = "heeellooo", words = ["hello", "hi", "helo"]

› Output: 1

💡 Note: "hello" can be stretched: h(1→1), e(1→3), l(2→2), o(1→3). "hi" fails because 'h' matches but 'i' doesn't match 'e'. "helo" fails because it's missing one 'l'.

Example 2 — No Valid Stretches

$ Input: s = "zzzzzyyyyy", words = ["zzyy", "zy", "zyy"]

› Output: 3

💡 Note: "zzyy": z(2→5)✓, y(2→5)✓. "zy": z(1→5)✓, y(1→5)✓. "zyy": z(1→5)✓, y(2→5)✓. All can be stretched to match the target.

Example 3 — Edge Case Single Character

$ Input: s = "aaa", words = ["a", "aa", "aaa"]

› Output: 2

💡 Note: "a" can be stretched to "aaa" (1→3). "aa" cannot be stretched because 2→3 requires at least 3 in target for extension. "aaa" matches exactly.

Constraints

1 ≤ s.length, words[i].length ≤ 50
1 ≤ words.length ≤ 50
s and words[i] consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Target string and array of query words

Process

Check each word to see if it can be stretched to match target

Output

Count of words that can be stretched

Key Takeaway

🎯 Key Insight: Compare character groups rather than individual characters, checking if groups can be stretched (extended to 3+ chars)

Asked in

G Google 42 f Facebook 28

The key insight is to compare character groups rather than individual characters. Use two pointers to process consecutive character groups, checking if each group in the query word can be stretched to match the target string (groups can only be extended to 3+ characters). Best approach is two-pointers with group comparison. Time: O(n × (m + k)), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers Group Comparison	O(n × (m + k))	O(1)	Use two pointers to efficiently compare character groups
Brute Force Character Comparison	O(n × m × k)	O(1)	Compare each character position with complex stretching logic

Two Pointers Group Comparison — Algorithm Steps

Initialize two pointers for both strings
Count consecutive characters in each group
Validate stretching conditions for each group
Move pointers to next group

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Pointers

Set pointers at start of both strings

Process Groups

Count consecutive characters in each group

Validate Rules

Check if stretching from word to target is valid

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isStretchy(const char* s, const char* word) {
    int i = 0, j = 0;
    int sLen = strlen(s), wordLen = strlen(word);
    
    while (i < sLen && j < wordLen) {
        if (s[i] != word[j]) {
            return false;
        }
        
        char ch = s[i];
        
        // Count in target string s
        int sCount = 0;
        while (i < sLen && s[i] == ch) {
            sCount++;
            i++;
        }
        
        // Count in query word
        int wordCount = 0;
        while (j < wordLen && word[j] == ch) {
            wordCount++;
            j++;
        }
        
        // Check stretching rules
        if (sCount < wordCount) {
            return false;
        }
        if (sCount != wordCount && sCount < 3) {
            return false;
        }
    }
    
    return i == sLen && j == wordLen;
}

int solution(const char* s, char words[][100], int wordCount) {
    int result = 0;
    for (int i = 0; i < wordCount; i++) {
        if (isStretchy(s, words[i])) {
            result++;
        }
    }
    return result;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char wordsLine[10000];
    fgets(wordsLine, sizeof(wordsLine), stdin);
    wordsLine[strcspn(wordsLine, "\n")] = 0;
    
    // Simple JSON parsing for array of strings
    char words[100][100];
    int wordCount = 0;
    
    char* token = strtok(wordsLine + 1, ",]");
    while (token != NULL && wordCount < 100) {
        // Remove quotes and spaces
        while (*token == ' ' || *token == '"') token++;
        int len = strlen(token);
        while (len > 0 && (token[len-1] == ' ' || token[len-1] == '"')) {
            token[len-1] = '\0';
            len--;
        }
        strcpy(words[wordCount], token);
        wordCount++;
        token = strtok(NULL, ",]");
    }
    
    int result = solution(s, words, wordCount);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × (m + k))

n words, each taking O(m + k) where m is word length and k is target string length

✓ Linear Growth

Space Complexity

O(1)

Only using variables for pointers and counters

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers Group Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler