Expressive Words
Expressive Words
You are given a target string s and a list of query strings words. A query string is considered "stretchy" if it can be transformed into the target string s by applying a specific extension operation any number of times. The extension operation allows you to choose a group of identical adjacent characters in the query string and add more of the same character to that group, provided the resulting group has a size of three or more.
For instance, if the query string is "hello" and the target string is "heeellooo":
- You can extend the group of 'e's (
"e") to"eee". - You can extend the group of 'o's (
"o") to"ooo".
This transforms "hello" into "heeellooo", making "hello" a stretchy word.
However, if a group in the query string has fewer than three characters and needs to be extended to match s, it's not a valid transformation. For example, if s requires a group of "oo" but the query word only has "o", you cannot extend it to "oo" because the initial group size must be less than three to be extended to three or more. The rule is: you can extend a group of identical characters c if its current size is less than 3, and the resulting size must be 3 or more. If the current size is already 3 or more, you can extend it further.
Your task is to count how many strings in the words array are stretchy with respect to the target string s.
Example 1:
Input: s = "heeellooo", words = ["hello", "hi", "helo"]
Output: 1
Explanation: "hello" is stretchy because 'e' can be extended to 'eee' and 'o' to 'ooo'. "helo" is not stretchy because the 'l' group in s is "ll" (size 2), and "hello" has "ll" (size 2), which cannot be extended to match s's "ll" group if s required a larger group of 'l's. Wait, the example explanation is slightly off. The rule is you can extend a group in the query word to match the target string. So, for s = "heeellooo" and word = "hello", we have groups h, e, ll, o. In s, we have h, eee, ll, ooo. The 'e' group in word (size 1) can be extended to eee (size 3). The 'o' group in word (size 1) can be extended to ooo (size 3). The 'll' group in word (size 2) matches the 'll' group in s (size 2). Thus, "hello" is stretchy. For word = "helo", we have groups h, e, l, o. In s, we have h, eee, ll, ooo. The 'l' group in word (size 1) cannot be extended to match s's 'll' group (size 2) because the extension rule requires the resulting group size to be 3 or more. This means if the target s has a group of size N, the query word must have a group of size M such that M <= N, and if N >= 3, then M must also be >= 1. If N < 3, then M must be equal to N. The rule is: a query word is stretchy if for every character group in s, the corresponding group in the query word has the same character, the same or smaller length, and if the length in s is 3 or more, the length in the query word can be 1 or more. If the length in s is less than 3, the length in the query word must match exactly.
Example 2:
Input: s = "zzzzzyyyyy", words = ["zzyy", "zy", "zyy"] Output: 3
Constraints:
1 <= s.length, words.length <= 1001 <= words[i].length <= 100sandwords[i]consist of lowercase letters.
Similar LeetCode problem: Expressive Words
AI interview prep
Core dilemma
Efficiently comparing compressed string representations while adhering to specific length constraints for character group expansions.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Expressive Words
Expressive Words
You are given a target string s and a list of query strings words. A query string is considered "stretchy" if it can be transformed into the target string s by applying a specific extension operation any number of times. The extension operation allows you to choose a group of identical adjacent characters in the query string and add more of the same character to that group, provided the resulting group has a size of three or more.
For instance, if the query string is "hello" and the target string is "heeellooo":
- You can extend the group of 'e's (
"e") to"eee". - You can extend the group of 'o's (
"o") to"ooo".
This transforms "hello" into "heeellooo", making "hello" a stretchy word.
However, if a group in the query string has fewer than three characters and needs to be extended to match s, it's not a valid transformation. For example, if s requires a group of "oo" but the query word only has "o", you cannot extend it to "oo" because the initial group size must be less than three to be extended to three or more. The rule is: you can extend a group of identical characters c if its current size is less than 3, and the resulting size must be 3 or more. If the current size is already 3 or more, you can extend it further.
Your task is to count how many strings in the words array are stretchy with respect to the target string s.
Example 1:
Input: s = "heeellooo", words = ["hello", "hi", "helo"]
Output: 1
Explanation: "hello" is stretchy because 'e' can be extended to 'eee' and 'o' to 'ooo'. "helo" is not stretchy because the 'l' group in s is "ll" (size 2), and "hello" has "ll" (size 2), which cannot be extended to match s's "ll" group if s required a larger group of 'l's. Wait, the example explanation is slightly off. The rule is you can extend a group in the query word to match the target string. So, for s = "heeellooo" and word = "hello", we have groups h, e, ll, o. In s, we have h, eee, ll, ooo. The 'e' group in word (size 1) can be extended to eee (size 3). The 'o' group in word (size 1) can be extended to ooo (size 3). The 'll' group in word (size 2) matches the 'll' group in s (size 2). Thus, "hello" is stretchy. For word = "helo", we have groups h, e, l, o. In s, we have h, eee, ll, ooo. The 'l' group in word (size 1) cannot be extended to match s's 'll' group (size 2) because the extension rule requires the resulting group size to be 3 or more. This means if the target s has a group of size N, the query word must have a group of size M such that M <= N, and if N >= 3, then M must also be >= 1. If N < 3, then M must be equal to N. The rule is: a query word is stretchy if for every character group in s, the corresponding group in the query word has the same character, the same or smaller length, and if the length in s is 3 or more, the length in the query word can be 1 or more. If the length in s is less than 3, the length in the query word must match exactly.
Example 2:
Input: s = "zzzzzyyyyy", words = ["zzyy", "zy", "zyy"] Output: 3
Constraints:
1 <= s.length, words.length <= 1001 <= words[i].length <= 100sandwords[i]consist of lowercase letters.
Similar LeetCode problem: Expressive Words