809. Expressive Words
Problem Description
The problem deals with determining if certain query words can be transformed into a specific target string by repeating characters within those words. This transformation follows a specific rule: a sequence of characters in the query word can be extended only if it results in a group of three or more of the same character in the target string. For example, if the target string is "heeellooo", the query word "hello" can be considered "stretchy" because it can be turned into the target string by repeating the 'e's and the 'o's to get "heeellooo".
To be more specific, if we have a group of characters in our target string, we can only extend the corresponding characters in our query word if the sequence length in the query word is either less than the target sequence and the target sequence has three or more characters, or it is exactly the same as that in the target sequence. So in our example, "hello" can be extended to "heeellooo" because the group "oo" is three or more characters, and the group "e" can also be extended because the original "e" in "hello" is less than the "ee" in "heeellooo" while "heeellooo" contains three or more "e"s.
The challenge is to determine how many words in a given list can be transformed in such a way into a given target string.
Intuition
The intuition behind solving this problem is to use two pointers: one for iterating over the characters of the target string s
and the other for iterating over the characters of a query word t
. The goal is to match groups of the same characters in s
and t
and validate whether the group in t
can be stretched to match the group in s
following the transformation rules defined by the problem.
Here's the step-by-step intuition for the approach:
- Iterate through each query word in the provided list and compare it against the target string.
- Use two pointers approach (let's call them
i
for the target strings
andj
for the query stringt
). - Compare characters at
i
andj
. If they are different, the word can't be stretched to match the string; hence it's not a "stretchy" word. - If the characters match, find the length of the consecutive group of the same character in both
s
andt
ā count how many times the character is repeated consecutively. - If the group in the target string
s
is at least three characters long or equal to the length of the group int
, and the group int
is not longer than that ins
, the characters could be expanded to match each other. - If a character in
s
is repeated less than three times and it's not the same count as int
, then it cannot be stretched to match, hence it's not a stretchy word. - Continue this process until the end of both the target string and the query word are reached.
- If the end of both strings is reached simultaneously, that means the word is stretchy; otherwise, it isn't.
- Count and return the number of words that can be stretched to match the target string.
Learn more about Two Pointers patterns.
Solution Approach
The code provided implements the stretchy words problem using a straightforward approach that matches the intuition previously detailed. Hereās how the implementation works:
-
Define a helper function
check(s, t)
that takes the target strings
and a query stringt
and returnsTrue
ift
can be stretched tos
, orFalse
otherwise. This function implements the two-pointer approach. -
Inside
check(s, t)
, initialize two pointers,i
for the target strings
andj
for the query stringt
. -
Loop through both strings while
i < len(s)
andj < len(t)
. For each character ats[i]
andt[j]
, do the following:-
If
s[i]
andt[j]
are different, returnFalse
as the current character cannot be stretched to match. -
If they match, find the length of the group of the same character in both strings by incrementing
i
andj
until the characters change. Let's call the lengthsc1
fors
andc2
fort
. -
Compare the lengths of these groups. If
c1 < c2
, the solution is immediatelyFalse
because we can't shorten characters in the target strings
. If the lengthc1
is 3 or greater, there's no issue, but ifc1
is less than 3 and also not equal toc2
, we can't stretcht
to matchs
; thus, the solution is alsoFalse
.
-
-
Once the while loop is terminated, the final check is
return i == len(s) and j == len(t)
, which ensures that both strings have been fully traversed and that they match up according to the problem rules. -
The main function
expressiveWords(s, words)
then applies thischeck(s, t)
function to each query stringt
in the listwords
. -
Use a list comprehension to apply the
check
function to each word inwords
, aggregating the number ofTrue
results, which corresponds to the count of stretchy words. -
Finally, return the sum as the answer to how many query strings are stretchy according to the target string
s
.
This solution employs the two pointers technique to facilitate the comparison between characters and groups of characters within the strings. It does not use any complex data structures, focusing instead on efficient iteration and comparison logic to solve the problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take the target string s = "heeellooo"
and the query words list words = ["hello", "hi", "helo"]
to illustrate the solution approach.
For the query word hello
:
- Pointers start at the beginning.
i = 0
for"heeellooo"
andj = 0
for"hello"
. - The first characters
h
match, but we need to check the following characters 'e'. - In
s
, it's followed by"ee"
making a group of 3 'e's before the next character 'l'. Int
, it's only one 'e'. - Since the group of 'e's in
s
is 3 or more, the single 'e' int
can be stretched. So we movei
to the next group ins
andj
to the next character int
, both at 'l'. - The 'l's match, and they are in the correct number so we continue.
- Then we check the 'o's. In
s
, we have a group of"ooo"
, and int
, we only have one 'o'. - The 'o' in
t
can be stretched because the group ins
has three or more 'o's. - We've reached the end of both strings simultaneously. So "hello" is a stretchy word.
For hi
:
- Characters 'h' match but then
i
points to character 'e' ins
andj
to character 'i' int
. - The characters are different and hence
hi
cannot be transformed intos
. So, "hi" is not a stretchy word.
For helo
:
- Characters 'h' match. Then we have one 'e' in both
s
andt
. - We meet the condition of having less than 3 'e's in
s
, but since both have the same count, we can move on. - Next, we have one 'l' in both
s
andt
, so we move on. - At the 'o's,
s
has a group of 3 'o's whilet
has only one. - Since the group of 'o's in
s
is 3 or more, we can stretch the 'o' int
. - We've reached the end of
t
but nots
. We have extra characters ins
("oo"
), so "helo" is not stretchy.
Following the implementation steps, we would use the helper function check(s, t)
for each word in words
, and only "hello" would return True
. Thus, the number of stretchy words in this example is 1.
Solution Implementation
1from typing import List
2
3class Solution:
4 def expressiveWords(self, original: str, words: List[str]) -> int:
5 # Function to check if a target word can be stretched to match the original word
6 def can_stretch(original: str, target: str) -> bool:
7 len_original, len_target = len(original), len(target)
8 # If the target word is longer than the original, it can't be stretched to match it
9 if len_target > len_original:
10 return False
11
12 index_original = index_target = 0
13
14 # Iterate over the characters of both the original and target words
15 while index_original < len_original and index_target < len_target:
16 if original[index_original] != target[index_target]:
17 return False # Characters do not match and can't be stretched
18
19 # Count the consecutive occurrences of the current character in the original word
20 count_original_char = index_original
21 while count_original_char < len_original and original[count_original_char] == original[index_original]:
22 count_original_char += 1
23 stretch_len = count_original_char - index_original
24
25 # Move to the corresponding character in the target word
26 index_original, count_target_char = count_original_char, index_target
27 while count_target_char < len_target and target[count_target_char] == target[index_target]:
28 count_target_char += 1
29 target_len = count_target_char - index_target
30 index_target = count_target_char
31
32 # Check the stretchability condition
33 # If stretch_len < 3, then the occurrences must match exactly
34 # If stretch_len >= 3, target_len should be at least 1 and not more than stretch_len
35 if (stretch_len < target_len or (stretch_len < 3 and stretch_len != target_len)):
36 return False
37
38 # Ensure we've reached the end of both words
39 return index_original == len_original and index_target == len_target
40
41 # Use a generator expression with sum to count how many words can be stretched
42 return sum(can_stretch(original, target) for target in words)
43
44
45# Example usage:
46solution = Solution()
47stretchy = solution.expressiveWords("heeellooo", ["hello", "hi", "helo"])
48print(stretchy) # This would print the number of stretchy words that match "heeellooo"
49
1class Solution {
2 public int expressiveWords(String s, String[] words) {
3 int expressiveWordCount = 0; // Initialize counter for expressive words
4
5 // Check each word in the array
6 for (String word : words) {
7 if (isExpressive(s, word)) {
8 expressiveWordCount++; // Increment count if word is expressive
9 }
10 }
11 return expressiveWordCount; // Return the total count
12 }
13
14 // Helper method to check if a given word is expressive
15 private boolean isExpressive(String s, String word) {
16 int sLength = s.length(), wordLength = word.length();
17
18 // If the length of word is greater than s, it cannot be expressive
19 if (wordLength > sLength) {
20 return false;
21 }
22
23 int i = 0, j = 0; // Pointers for iterating over the characters of s and word
24 while (i < sLength && j < wordLength) {
25 // Compare characters of s and word at the current pointers
26 if (s.charAt(i) != word.charAt(j)) {
27 return false; // If they don't match, the word is not expressive
28 }
29 // Count the number of consecutive identical chars from current pointer in s
30 int runLengthS = i;
31 while (runLengthS < sLength && s.charAt(runLengthS) == s.charAt(i)) {
32 runLengthS++;
33 }
34 int sNum = runLengthS - i; // The count of consecutive characters in s
35 i = runLengthS;
36
37 // Similarly, count consecutive identical chars from current pointer in word
38 int runLengthWord = j;
39 while (runLengthWord < wordLength && word.charAt(runLengthWord) == word.charAt(j)) {
40 runLengthWord++;
41 }
42 int wordNum = runLengthWord - j; // The count of consecutive characters in word
43 j = runLengthWord;
44
45 // If s has fewer chars in the run or the run is less than 3 and different, return false
46 if (sNum < wordNum || (sNum < 3 && sNum != wordNum)) {
47 return false;
48 }
49 }
50 // Ensure both strings have been fully traversed
51 return i == sLength && j == wordLength;
52 }
53}
54
1class Solution {
2public:
3 /**
4 * Counts how many words can be stretched to match the string S.
5 *
6 * @param S The original string.
7 * @param words A list of words to compare to S.
8 * @return The count of expressive words.
9 */
10 int expressiveWords(string S, vector<string>& words) {
11 // Lambda function to check if t can be stretched to match s.
12 auto isStretchy = [](const string& s, const string& t) -> bool {
13 int sLength = s.size(), tLength = t.size();
14
15 // If t is longer than s, we cannot stretch t to match s.
16 if (tLength > sLength) return false;
17
18 int i = 0, j = 0; // Pointers for s and t.
19
20 // Iterate over both strings.
21 while (i < sLength && j < tLength) {
22 // If the characters at the current pointers don't match, return false.
23 if (s[i] != t[j]) return false;
24
25 // Count the number of consecutive characters in s.
26 int runStartS = i;
27 while (i < sLength && s[i] == s[runStartS]) ++i;
28 int countS = i - runStartS;
29
30 // Count the number of consecutive characters in t.
31 int runStartT = j;
32 while (j < tLength && t[j] == t[runStartT]) ++j;
33 int countT = j - runStartT;
34
35 // Check if the run in s can be stretched to match t's run or not.
36 // If s's run is shorter than t's, or if s's run is not stretchy (countS < 3) and not equal to t's run, return false.
37 if (countS < countT || (countS < 3 && countS != countT)) return false;
38 }
39
40 // If we've reached the end of both s and t, return true, otherwise return false.
41 return i == sLength && j == tLength;
42 };
43
44 // Count the number of words that are stretchy.
45 int expressiveCount = 0;
46 for (const string& word : words) {
47 if (isStretchy(S, word)) {
48 expressiveCount++;
49 }
50 }
51
52 return expressiveCount;
53 }
54};
55
1/**
2 * Counts how many words can be stretched to match the string originalString.
3 *
4 * @param originalString The original string.
5 * @param words A list of words to compare to originalString.
6 * @return The count of expressive words.
7 */
8function expressiveWords(originalString: string, words: string[]): number {
9 // Function to check if target can be stretched to match source string.
10 let isStretchy = (source: string, target: string): boolean => {
11 let sourceLength = source.length, targetLength = target.length;
12
13 // If target is longer than source, it cannot be stretched to match source.
14 if (targetLength > sourceLength) return false;
15
16 let i = 0, j = 0; // Pointers for source and target strings.
17
18 // Iterate over both strings
19 while (i < sourceLength && j < targetLength) {
20 // If characters at current pointers don't match, return false.
21 if (source[i] !== target[j]) return false;
22
23 // Count the number of consecutive characters in source.
24 let runStartSource = i;
25 while (i < sourceLength && source[i] === source[runStartSource]) i++;
26 let countSource = i - runStartSource;
27
28 // Count the number of consecutive characters in target.
29 let runStartTarget = j;
30 while (j < targetLength && target[j] === target[runStartTarget]) j++;
31 let countTarget = j - runStartTarget;
32
33 // Check if the run in source can be stretched to match target's run.
34 // If source's run is shorter than target's, or if source's run is not stretchable (countSource < 3) and not equal to target's run, return false.
35 if (countSource < countTarget || (countSource < 3 && countSource !== countTarget)) return false;
36 }
37
38 // If we've reached the end of both source and target, return true.
39 return i === sourceLength && j === targetLength;
40 };
41
42 // Count the number of words that can be stretched.
43 let expressiveCount = 0;
44 for (const word of words) {
45 if (isStretchy(originalString, word)) {
46 expressiveCount++;
47 }
48 }
49
50 return expressiveCount;
51}
52
53// Example usage:
54const originalString = "heeellooo";
55const words = ["hello", "hi", "helo"];
56console.log(expressiveWords(originalString, words)); // Output should be the count of expressive words that match 'originalString'
57
Time and Space Complexity
The time complexity of the expressiveWords
function depends mainly on two parameters: the length of the string s
and the total number of characters in all the words in the words
list. Let's denote the length of string s
as M
and the total number of characters in the words
list as N
.
The check
function, which is called for each word in words
, runs with two pointers, i
and j
, iterating over the characters of s
and the current word, respectively. In the worst case, both pointers have to go through the entire length of s
and the word. The inner while loops increase the pointer k
to skip over repeated characters and compute the counts c1
and c2
, but they do not add to the asymptotic complexity since they simply advance the corresponding pointer i
or j
.
Therefore, for a single call, check
has a time complexity of O(M)
, where M
is the length of the string s
. Since check
is called once for each word, with the total length being N
, the overall time complexity for all calls to check
is O(N * M)
.
The space complexity of the algorithm is O(1)
since only a fixed number of variables are used and they do not depend on the size of the inputs. The space required to hold pointers, counts, and other variables is constant and does not grow with the size of the input.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the minimum element can be found in:
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!