Frontend School

Repetitive String Matcher

DSA
medium

Repetitive String Matcher

Medium
String

Overview

In user-generated content platforms like Sharechat, users often express themselves with creative variations in text, such as repeating characters for emphasis (e.g., "cooool" instead of "cool"). To provide robust search, content moderation, or trend analysis, it's crucial to identify when two strings are fundamentally similar despite these superficial repetitions. This problem challenges you to implement a core component for such a system.

What you need to do / Task

Implement a function isRepetitiveMatch(word: string, pattern: string) that determines if a given word repetitively matches a pattern string according to two specific rules. The function should return true if word matches pattern, and false otherwise.

Rules for Repetitive Matching:

  1. Normalized Form Identity: Both word and pattern must normalize to the exact same string. The normalized form is obtained by reducing all sequences of consecutive identical characters to a single instance (e.g., "heeelloo" normalizes to "helo", "coool" normalizes to "col").
  2. Repetition Count Sufficiency: For each corresponding character block in their normalized forms, the count of consecutive identical characters in the word must be greater than or equal to the count of the same character in the pattern.

Input & output

  • word: A string representing the input word to be checked.
  • pattern: A string representing the pattern to match against.
  • Returns: boolean - true if word repetitively matches pattern based on the given rules, false otherwise.

Clarifications

  • Empty Strings: An empty string normalizes to an empty string. An empty string is considered to repetitively match only another empty string.
  • Case Sensitivity: All character comparisons are case-sensitive.
  • Character Set: Strings will consist of lowercase English letters only.

Examples

1

Example 1

Input:

word = "heeelloo", pattern = "helo"

Output:

true

Note:

Normalized forms for both are "helo". 'h': word (1) >= pattern (1). OK. 'e': word (3) >= pattern (1). OK. 'l': word (2) >= pattern (1). OK. 'o': word (2) >= pattern (1). OK.

2

Example 2

Input:

word = "ab", pattern = "aab"

Output:

false

Note:

Normalized forms for both are "ab". 'a': word (1) >= pattern (2) is FALSE. Thus, it's not a match.

3

Example 3

Input:

word = "apple", pattern = "aple"

Output:

true

Note:

Normalized forms for both are "aple". 'a': word (1) >= pattern (1). OK. 'p': word (2) >= pattern (1). OK. 'l': word (1) >= pattern (1). OK. 'e': word (1) >= pattern (1). OK.

4

Example 4

Input:

word = "", pattern = ""

Output:

true

Note:

Both are empty strings, which normalize to empty and satisfy the count condition vacuously.

Constraints

Constraints & assumptions

  • 1 <= word.length, pattern.length <= 10^4 (for non-empty cases)
  • word and pattern consist of lowercase English letters ('a'-'z').

What interviewers evaluate

  • Correctness in implementing the string normalization and comparison logic.
  • Efficiency of the algorithm (should achieve linear time complexity relative to string lengths).
  • Clarity, modularity, and readability of the code (e.g., use of helper functions).
  • Thoroughness in handling edge cases, such as empty strings or strings with single character repetitions.

Loading editor...