Find All Anagrams in a Text

medium Strings

Problem

Two lowercase words are given: a text and a pattern. Print the start index of every part of the text that is an anagram of the pattern (the same letters in any order), from the smallest index to the biggest, separated by spaces. Print none if there is no such part. Use a sliding window with letter counts: O(n).

Constraints

  • 1 <= lengths <= 10^5
  • lowercase letters

Examples

Input

cbaebabacd abc

Output

0 6

Solutions

Best approachTime O(n)Space O(1)

Sorting every part of the text would cost O(n * m log m). The window only changes by two letters at each step, so comparing two arrays of 26 counts (a constant) gives O(n).

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process two words.
 * Input   : Two words separated by a space.
 * Output  : Start indexes or none.
 * Approach: A text and a pattern.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String solve(String a, String b) {
        // Step 1: If the pattern is longer than the text, no part can match.
        if (b.length() > a.length()) {
            return "none";
        }
        // Step 2: "need" counts the letters of the pattern. "window" counts the letters in the current part of the text.
        int[] need = new int[26];
        int[] window = new int[26];
        for (int i = 0; i < b.length(); i++) {
            need[b.charAt(i) - 'a']++;
            window[a.charAt(i) - 'a']++;
        }
        StringBuilder result = new StringBuilder();
        for (int start = 0; ; start++) {
            // Step 3: The part is an anagram when both counts are equal.
            if (java.util.Arrays.equals(need, window)) {
                result.append(result.length() == 0 ? "" : " ").append(start);
            }
            // Step 4: Slide by one: add the next letter on the right and remove the first letter on the left.
            int next = start + b.length();
            if (next >= a.length()) {
                break;
            }
            window[a.charAt(next) - 'a']++;
            window[a.charAt(start) - 'a']--;
        }
        return result.length() == 0 ? "none" : result.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String a = scanner.next();
        String b = scanner.next();
        System.out.println(solve(a, b));
    }
}
Hints (1)
  1. Why do two count arrays of size 26 count as constant work?