Code Destine

Problem Statement

You have given two strings S and T, find out all the start indices of S anagrams in T.

Note :- Strings consists of only lowercase English letters.

Example 

Input :- S = "abc" T = "cbaebabacd"
Output :- [0, 6]

Input :- S = "ab" T = "abab"
Output :- [0, 1, 2]

Solution

This problem can be solved in following steps :-

1. Create the character array from the input String S.
2. Create an integer array (count array) of size 26 (Total number of characters in the English language), This array will be used to store the frequency of each character in the input string.
3. Traverse the character array S from start (index 0) to end (n-1, where n is the length of an array) and convert each character into an index of count array by subtracting the character from ‘a’ and converting it into ASCII code. Increase the count for the calculated index by 1.
4. Create the character array from the input String T.
5. Traverse the character array T to find out the start indices of anagrams and return the list.

Program

import java.util.ArrayList;
import java.util.List;

public class Main {

	public static void main(String[] args) {		
		Main main = new Main();
		List<Integer> result = main.findAnagrams("cbaebabacd", "abc");
		for(Integer i : result) {
			System.out.print(i + ", ");
		}
	}
	
	/* Solution */
	public List<Integer> findAnagrams(String t, String s) {
        
        char[] pArray = s.toCharArray();
        int[] countArray = new int[26];
        for(int j=0; j<pArray.length; j++){
            countArray[pArray[j]-'a']++;
        }
        
        boolean isPresent = true;
        List<Integer> result = new ArrayList<>();
        int[] arr = null;        
        char[] sArray = t.toCharArray();
        for(int i=0; i<(sArray.length-pArray.length+1); i++){
            if(countArray[sArray[i]-'a'] > 0){
                isPresent = true;
                arr = countArray.clone();            
                for(int j=0; j<pArray.length; j++){
                    arr[sArray[i+j]-'a']--;
                }
                
                for(int j=0; j<arr.length; j++){
                    if(arr[j] != 0){
                        isPresent = false;
                        break;
                    }
                }
                
                if(isPresent){
                    result.add(i);
                }
                
            }            
        }
        return result;
    }
}

Result

0, 6, 

Similar Post

1. Group Anagrams
2. Reverse Vowels of a String
3. Custom Order Sorting of String

That’s all for Find All Anagrams in a String in Java, If you liked it, please share your thoughts in a comments section and share it with others too.