Expressive Words

Expressive Words

What is this problem about?

The Expressive Words interview question involves "stretchy" words. A word is stretchy if you can take any group of identical consecutive characters and lengthen the group to 3 or more characters. For example, "hello" can be stretched to "helllooo" (3 'l's, 3 'o's) but not "hhello" (only 2 'h's). You are given a target string s and a list of words. You need to count how many words in the list can be stretched to match s.

Why is this asked in interviews?

Companies like Google and Cisco use this String coding problem to test your ability to group and compare character sequences. It evaluates whether you can effectively use Two Pointers or group-based analysis. It requires careful handling of edge cases, such as when a group in the original word is already longer than the target or when the character counts don't allow for a valid stretch.

Algorithmic pattern used

The problem uses a Two Pointers / Run-Length Encoding pattern.

1. Compare the target s and a word w group by group.
2. For each corresponding group of characters:
   • The characters must be identical.
   • Let c1 be the count in s and c2 be the count in w.
   • If c1 < c2, it's impossible (cannot shrink).
   • If c1 > c2 and c1 < 3, it's impossible (stretching must result in at least 3 chars).
3. If all groups match these conditions, the word is "stretchy."

Example explanation

s = "heeellooo", words = ["hello", "hi"]

1. For "hello":
   • 'h': count in s=1, w=1. (Match).
   • 'e': count in s=3, w=1. c1 >= 3 and c1 > c2. (Stretched, OK).
   • 'l': count in s=2, w=2. (Match).
   • 'o': count in s=3, w=1. c1 >= 3. (Stretched, OK). Result: "hello" is valid.
2. For "hi":
   • 'h': Match.
   • 'i': 'i' doesn't exist at this position in s. Result: "hi" is invalid.

Common mistakes candidates make

• Missing the "3 or more" rule: Thinking any stretch is allowed, when the rule specifically states the resulting group must be at least length 3.
• Ignoring existing length: Failing to check if c2 > c1, which is invalid because you can only add characters, not remove them.
• Incomplete comparison: Forgetting to check if both strings were fully consumed after the group checks.

Interview preparation tip

Whenever you process strings with repeating characters, think about "Run-Length Encoding" (representing "aaabb" as (a, 3), (b, 2)). This often simplifies the comparison logic significantly.