Frontend School

Find Anagram Substrings with Wildcard

DSA
medium

Find Anagram Substrings with Wildcard

Medium
String
Sliding Window
Hash Map
frequency count

Overview

In Uber's ride-hailing platform, ensuring data consistency and efficient search is crucial. Imagine a scenario where we need to identify specific patterns in driver or rider profiles, but with some flexibility. This problem asks you to find all occurrences of a pattern (which can include a wildcard) as an anagram within a larger text, mimicking a real-world need for flexible pattern matching.

What you need to do / Task

Your task is to implement a function findAnagramSubstrings that takes two strings: text and pattern. The pattern string may contain a special wildcard character ?. This wildcard matches any single character. You need to find all starting indices in the text where a substring of text is an anagram of the pattern, considering the wildcard.

Specifically:

  1. A substring of text is considered an anagram of pattern if it has the same length as pattern.
  2. For every non-wildcard character c in pattern, its frequency in the substring must be at least its frequency in the pattern.
  3. The ? wildcard in pattern means that its corresponding position in the substring can be filled by any character. The total number of characters in the substring that are not explicitly required by the non-wildcard characters in pattern (i.e., excess characters beyond the minimum required counts) must exactly match the total number of ? wildcards in the pattern.

Input & output

Function Signature: function findAnagramSubstrings(text: string, pattern: string): number[]

Parameters:

  • text: A string representing the main text to search within. It consists only of lowercase English letters ('a'-'z').
  • pattern: A string representing the pattern to find anagrams of. It consists only of lowercase English letters ('a'-'z') and the wildcard character '?'.

Return Value:

  • An array of numbers, representing the 0-indexed starting positions in text where an anagram of pattern is found. The array should be sorted in ascending order.

Clarifications

  • The wildcard ? can only appear in the pattern string, not in text.
  • The problem is case-sensitive (though inputs are restricted to lowercase English letters).
  • If pattern.length is greater than text.length, no matches are possible, and an empty array should be returned.

Examples

1

Example 1

Input:

text = "cbaebabacd", pattern = "abc"

Output:

[0,6]

Note:

The substring at index 0 is "cba", which is an anagram of "abc". The substring at index 6 is "bac", which is an anagram of "abc".

2

Example 2

Input:

text = "abaacb", pattern = "a?b"

Output:

[0,1,3]

Note:

Pattern "a?b" means we need one 'a', one 'b', and one wildcard character.

  • Index 0: "aba". Contains two 'a's and one 'b'. One 'a' satisfies the 'a' requirement, one 'b' satisfies the 'b' requirement. The extra 'a' is matched by the wildcard. Valid.
  • Index 1: "baa". Contains two 'a's and one 'b'. Similar to index 0, valid.
  • Index 2: "aac". Contains two 'a's and one 'c'. Does not contain 'b'. Invalid.
  • Index 3: "acb". Contains one 'a', one 'c', one 'b'. One 'a' and one 'b' satisfy requirements. The 'c' is matched by the wildcard. Valid.
3

Example 3

Input:

text = "zzza", pattern = "???"

Output:

[0,1]

Note:

Pattern "???" means any 3 characters. All characters are matched by wildcards.

  • Index 0: "zzz". Matches.
  • Index 1: "zza". Matches.

Constraints

Constraints & assumptions

  • 1 <= text.length <= 10^5
  • 1 <= pattern.length <= 10^5
  • pattern.length <= text.length
  • text consists only of lowercase English letters ('a'-'z')
  • pattern consists only of lowercase English letters ('a'-'z') and the wildcard character '?'

What interviewers evaluate

  • Correctness: The solution accurately identifies all valid anagram substrings according to the problem definition, especially handling the wildcard correctly.
  • Efficiency: The solution uses an optimal approach (e.g., sliding window) with appropriate time and space complexity, avoiding brute-force for large inputs.
  • Code Quality: The code is well-structured, readable, and handles edge cases gracefully.
  • Problem-Solving: Demonstrates a clear understanding of string manipulation, frequency counting, and sliding window techniques.

Loading editor...