Find All Anagrams in a String

Given two strings s and p, return an array of all the start indices of p’s anagrams in s.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Input Format:

The first line contains a single integer n(length of string s).

Second line contains string s.

Third line contains a single integer m(length of string p).

Fourth line contains string p.

Output Format:

Print all the starting indexes of p’s anagram in s in sorted order.

Example 1

Input

10
cbaebabacd
3
abc

Output

0 6 

Explanation

The substring with start index = 0 is “cba”, which is an anagram of “abc”.

The substring with start index = 6 is “bac”, which is an anagram of “abc”.

Example 2

Input

4
abab
2
ab

Output

0 1 2

Explanation

The substring with start index = 0 is “ab”, which is an anagram of “ab”.

The substring with start index = 1 is “ba”, which is an anagram of “ab”.

The substring with start index = 2 is “ab”, which is an anagram of “ab”.

Constraints

1 <= s.length, p.length <= 3 * 10^4

sand p consists of lowercase English letters.

Solution of Find All Anagrams in a String: —

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		//your code here
                 Scanner sc = new Scanner(System.in);
                int x [] = new int[26], y []= new int[26];
                for(int i=0;i<26;i++){
                        x[i] = 0;
                        y[i] = 0;
                }
                int n = sc.nextInt();
                String a = sc.next();
                n = a.length();
                int m = sc.nextInt();
                String b = sc.next();
                m = b.length();

                if(n<m) return;

                for(int i=0;i<m;i++){
                        y[b.charAt(i)-'a']++;
                        x[a.charAt(i)-'a']++;
                }
                if(check(x,y)==true) 
                        System.out.print(0 + " ");

                for(int i=m;i<n;i++){
                        x[a.charAt(i)-'a']++;
                        x[a.charAt(i-m)-'a']--;

                        if(check(x,y)==true)
                                System.out.print(i-m+1 + " ");
                }
	}
        static boolean check(int [] x, int [] y){
                for(int i=0;i<26;i++){
                        if(x[i]!=y[i])
                                return false;
                }
                return true;

	}
}