Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 2: String Anagrams (hard)

Problem Statement

Given a string and a pattern, find all anagrams of the pattern in the given string.

Every anagram is a permutation of a string. As we know, when we are not allowed to repeat characters while finding permutations of a string, we get N! permutations (or anagrams) of a string having N characters. For example, here are the six anagrams of the string abc:

  1. abc
  2. acb
  3. bac
  4. bca
  5. cab
  6. cba

Write a function to return a list of starting indices of the anagrams of the pattern in the given string.

Example 1:

.....

.....

.....

Like the course? Get enrolled and start learning!
F

First

· 4 years ago

For this question, if we find multiple matches, how come we don't repopulate the map, after each successful match?

A

arya.javadi80

· 3 years ago

Why do we put the character of the winodw_start back in the hashmap, when trying to shorten the sliding window?

M

Meghana

· 4 years ago

Why is the case, where we find a character that is not in the hash map 'charFrequency', is not handled? Is it not required or is it assumed that we should handle it? If it is not required, please explain why.

Show 1 reply
D

Dee

· 5 years ago

Why is matched compared to the number of keys in the charFrequency instead of the length of the pattern? Can the pattern not have repeating characters such as “ aabc” vs just “abc”?

Show 2 replies
B

Bipra

· 4 years ago

Assuming the input string and pattern is in lowercase alphabets, here is the golfing solution

var result []int patternFrequency := [26]int{} charFrequency := [26]int{} for _, c := range pattern { patternFrequency[c-97] += 1 } for i := 0; i < len(pattern); i++ { charFrequency[input[i]-97]++ } if charFrequency == patternFrequency { result = append(result, 0) } for i := 1; i

J

Jared

· 4 years ago

for the python solution, why is it result_indices.append(window_start) and not window_end?

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

import math
from collections import Counter

class Solution:
  def findStringAnagrams(self, text, pattern):
    result = []
    if text == "":
      return result 

    # pattern frequency count
    pattern_counter = Counter(pattern)

    # initial window frequency count
    text_counter = {}
    for i in range(len(pattern)):
      text_counter[text[i]] = text_counter.get(text[i], 0)
      text_counter[text[i]] += 1

    i = len(pattern) - 1
    j = 0
    
    while i < len(text):
      # if counters match we have an anagram
      if text_counter == pattern_counter:
        result.append(j)
      
      # move i then add the i frequency to the map
      i += 1
      if i == len(text):
        break
      text_counter[text[i]] = text_counter.get(text[i], 0)
      text_counter[
Sachin Dev S

Sachin Dev S

· 2 years ago

should this not be windowStart-windowEnd+1 which gives the size and then compare it with the size of the pattern?

after a while it will always be true

Sachin Dev S

Sachin Dev S

· 2 years ago


import java.util.*;

class Solution {
    public List<Integer> findStringAnagrams(String str, String pattern) {
      List<Integer> resultIndices = new ArrayList<Integer>();

      Map<Character, Integer> patternMap = new HashMap<>();
      for(Character c: pattern.toCharArray()) {
        patternMap.put(c, patternMap.getOrDefault(c, 0)+1);
      }

      char[] arr = str.toCharArray();
      int n = arr.length, plen = pattern.length();
      Map<Character, Integer> map = new HashMap<>();
      for(int i = 0; i < plen; i ++) {
        map.put(arr[i], map.getOrDefault(arr[i], 0)+1);
      }

      if(isMatch(map, patternMap)) {
        resultIndices.add(0);
      }

      int st = 0;
      for(int end = plen; end < n; end++) {
        map.put(arr[end], map.getOrDefault(arr[end], 0)
Enrique Fernández

Enrique Fernández

· 2 years ago

import math

from collections import Counter, defaultdict

class Solution:
  def findStringAnagrams(self, str1, pattern):
    result_indices = []
    # TODO: Write your code here
    
    patternReps = Counter(pattern)
    windowReps = defaultdict(int)
    start = 0
    for end in range(len(str1)):
      windowReps[str1[end]] += 1

      if end - start + 1 == len(pattern):
        if patternReps == windowReps:
          result_indices.append(start)

        windowReps[str1[start]] -= 1
        if windowReps[str1[start]] == 0:
          del windowReps[str1[start]]
        start += 1    

    return result_indices