#809

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Expressive Words

Expressive Words challenges you to determine if a word can be transformed into a given string by extending groups of repeated characters.

array two pointers string

Problem Statement

You are given a string s and an array of query strings words. A word from the array is considered stretchy if it can be transformed into s by applying a specific extension operation. This operation allows you to choose a group of adjacent identical characters in the word and extend them, but the group must have at least three characters after extension.

For example, the word 'heeellooo' can be turned into 'hello' by extending the 'e' group to three 'e's and the 'o' group to three 'o's. Your task is to determine how many of the words in the list can be transformed into s.

Examples

Example 1

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

Output: 1

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

Example details omitted.

Constraints

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

Solution Approach

Two-pointer approach

Use a two-pointer technique to scan through both s and each word in words. As you compare characters, check if the groups of repeated characters match and if they can be extended according to the rules.

Invariant tracking

Track the invariants of the groups of repeated characters in both s and each word. Ensure that the number of repetitions in each group matches and can be extended to meet the minimum size requirement of three.

Edge case handling

Handle edge cases such as very short strings or words with no repeating characters. These cases should be properly filtered out in the algorithm.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of words and the length of each word. The two-pointer approach ensures that each character is processed only once, making the overall time complexity O(n * m), where n is the number of words and m is the average length of the words. Space complexity is O(1) as no extra space is required aside from the input and output.

What Interviewers Usually Probe

Ability to implement two-pointer scanning effectively.
Comfort with tracking invariants across two strings during comparison.
Understanding of edge cases and how they affect the algorithm.

Common Pitfalls or Variants

Common pitfalls

Not correctly handling edge cases where groups of characters do not meet the required size for extension.
Incorrectly tracking character groups, leading to false negatives for valid words.
Confusing the requirement for extensions with simple character repetition without extension.

Follow-up variants

Extend the problem to handle case-insensitive strings or strings with mixed characters.
Introduce more complex constraints such as words with non-alphabetical characters.
Change the minimum group extension requirement to a different threshold, such as 2 or 4 characters.

FAQ

How can I solve the Expressive Words problem using two-pointer scanning?

You can solve the problem by using two pointers to compare the groups of repeated characters in the given string s and each word. The pointers help track the length of each group and ensure the correct number of extensions for matching.

What is the time complexity of solving the Expressive Words problem?

The time complexity is O(n * m), where n is the number of words and m is the average length of the words, due to the two-pointer approach processing each character once.

What does the invariant tracking technique refer to in Expressive Words?

Invariant tracking refers to monitoring the groups of repeated characters in both the target string s and each word, ensuring that they match and can be extended according to the given rules.

What are some common mistakes when solving the Expressive Words problem?

Common mistakes include failing to handle edge cases like non-repeating characters or incorrect extension of character groups that don't meet the minimum required size.

How does GhostInterview help with the Expressive Words problem?

GhostInterview helps by guiding you through the two-pointer scanning approach, assisting in invariant tracking, and providing practice scenarios to handle edge cases in your solution.

terminal

Solution

Solution 1: Traversal Counting + Two Pointers

We can traverse the array $\textit{words}$, and for each word $t$ in the array, check if $t$ can be expanded to obtain $s$. If it can, increment the answer by one.

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:
        def check(s, t):
            m, n = len(s), len(t)
            if n > m:
                return False
            i = j = 0
            while i < m and j < n:
                if s[i] != t[j]:
                    return False
                k = i
                while k < m and s[k] == s[i]:
                    k += 1
                c1 = k - i
                i, k = k, j
                while k < n and t[k] == t[j]:
                    k += 1
                c2 = k - j
                j = k
                if c1 < c2 or (c1 < 3 and c1 != c2):
                    return False
            return i == m and j == n

        return sum(check(s, t) for t in words)

Continue Practicing

#821 shortest distance to a character #942 di string match #1023 camelcase matching