algoadvance

Leetcode 809. Expressive Words

Problem Statement

Sometimes people repeat letters to represent extra feeling, such as “hello” -> “heeellooo”. In these strings, we may have more than one group of repeated characters, for example “heeellooo” -> “heeellooo”. Let’s define the “stretch” of a group as the length of this contiguous substring. For example, the string “heeellooo” has stretches of “h” -> 1, “e” -> 3, “l” -> 2, “o” -> 3.

Consider the following informal example:

A word is stretchy if it can be made to match S by any number of insertions of characters into S. An expressive word must be such that any occurrences of a character can be extended to match S.

Formally, we can say a word is stretchy if:

  1. For each group of characters in the word, the corresponding group in S has at least the same number of characters.
  2. If the group in S’s length is greater than the group in the word by more than a small amount, then it is stretchable only if the length in S is 3 or more.

The task is to write a function that counts how many words from the given list are stretchy for a given string S.

You are given:

You need to return:

Clarifying Questions

  1. Will the input string S and the strings in the words list contain only lowercase English letters?
    • Yes, all input strings consist only of lowercase English letters.
  2. Is the words list guaranteed to be non-empty?
    • Yes, words will always contain at least one word.

Code

#include <vector>
#include <string>
using namespace std;

bool isStretchy(const string &S, const string &word) {
    int n = S.size();
    int m = word.size();
    int i = 0, j = 0;

    while (i < n && j < m) {
        if (S[i] != word[j]) {
            return false;
        }

        int len1 = 0;
        while (i + len1 < n && S[i + len1] == S[i]) {
            len1++;
        }

        int len2 = 0;
        while (j + len2 < m && word[j + len2] == word[j]) {
            len2++;
        }

        if ((len2 > len1) || (len1 < 3 && len1 != len2)) {
            return false;
        }
        i += len1;
        j += len2;
    }

    return i == n && j == m;
}

int expressiveWords(string S, vector<string> &words) {
    int count = 0;
    for (const string &word : words) {
        if (isStretchy(S, word)) {
            count++;
        }
    }
    return count;
}

Strategy

  1. Initialize Pointers: Use two pointers i and j to traverse S and the current word respectively.
  2. Check Character Matches: If characters at S[i] and word[j] do not match, the word is not stretchy.
  3. Count Consecutive Characters: Count the consecutive repeated characters in both the original string S and the current word.
  4. Stretchy Conditions Check:
    • The length of the sequence in S must be greater than or equal to the length in the word.
    • If the sequence in S is exactly 2 characters long, it can’t be stretched unless it’s already equal in length to the word’s sequence.
    • If the sequence in S is 3 or more characters long, it can be stretched as required.
  5. Check End of Strings: Both pointers should reach the end of their respective strings for the word to be stretchy.
  6. Count Matching Words: For each word in the list, check if it is stretchy and maintain a count.

Time Complexity

This approach efficiently checks each word in the list and verifies if it’s a stretchy version of S.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI