Sub Array Contains Anagram


  • 0
    M

    Given 2 words, return true if second word has a substring that is also an anagram of word 1.
    LGE , GOOGLE- True
    GEO, GOOGLE - False


  • 0
    M
    import java.util.*;
    
    public class Main{
    
      public static void main(String[] args){
        System.out.println(checkAnagram("OGE","GOOGLE"));
      }
      
      public static boolean checkAnagram(String input, String input1){
    	String longestString = input;
    	String shortestString = input1;
    	if(input.length() < input1.length()){
    		longestString = input1;
    		shortestString = input;
    	}	
    
    	List<String> subStrings = new ArrayList<>();
    	for(int i=0; i< longestString.length();i++){
    		if(i+shortestString.length() <=longestString.length()){
    			subStrings.add(longestString.substring(i,i+shortestString.length()));
    		}
    	}
    		
    	for(String subString: subStrings){
    		HashMap<Character, Integer> map = new HashMap<>();
    		for(Character character :subString.toCharArray()){
    			if(map.containsKey(character)){
    				map.put(character, map.get(character)+1);
    			}else{
    				map.put(character,1);
    			}
    		}
    
    		boolean check = true;
    		for(Character c :shortestString.toCharArray()){
    			if(!map.containsKey(c)){
    				check = false;
    				break;
    			}else{
    				if(map.get(c) > 0){
    					map.put(c, map.get(c)-1);
    				}else{
    					check = false;
    					break;
    				}
    			}
    		}
    		if(check){
    			return true;
    		}
    	}
    	return false;
    }
    
      
      
      
    }
    

  • 0
    M

    Time complexity of above code is O(mn).. can this be even be optimized?


  • 0
    E

    @mleavoyraja.p You could use a sliding window and a hash of character occurrences for O(n) complexity.


  • 0
    S

    This is with O(n) time complexity . This program is modification to Min window sub string

     public string CheckAnagram(string s, string pattern)
            {
                var map = new Dictionary<char, int>();
    
                foreach (var c in pattern)
                {
                    int val;
                    if(map.TryGetValue(c, out val))
                    {
                        map[c]++;
                    }
                    else
                    {
                        map.Add(c, 1);
                    }
                }
    
                // counter represents the number of chars of t to be found in s.
                int start = 0, end = 0;
                int counter = pattern.Length, minStart = 0, minLen = int.MaxValue;
                int size = s.Length;
    
                // Move end to find a valid window.
                while (end < size)
                {
                    int val;
                    // If char in s exists in pattern, decrease counter
                    if (map.TryGetValue(s[end], out val))
                    {
                        if (val >= 1)
                        {
                            counter--;
                        }
                    }
    
                    // If char does not exist in pattern, m[s[end]] will be negative.
                    if (map.ContainsKey(s[end]))
                    {
                        map[s[end]]--;
                    }
                    else
                    {
                        map.Add(s[end], -1);
                    }
    
                    end++;
    
                    // When we found a valid window, move start to find smaller window.
                    while (counter == 0)
                    {
                        if (end - start < minLen)
                        {
                            minStart = start;
                            minLen = end - start;
                        }
    
                        map[s[start]]++;
    
                        // When char exists in pattern, increase counter.
                        if (map[s[start]] >= 1)
                        {
                            counter++;
                        }
                        start++;
                    }
                }
    
                //We found valid window but print only if it matches the pattern size
                if (minLen == pattern.Length)
                {
                    return s.Substring(minStart, minLen);
                    //return true;
                }
    
                //return false;
                return "";
            }
    

  • 0
    R

    O(N) with slide window and hash

    def judge(self,table1,table2):
        for keys in table1:
            if not keys in table2:
                return False
            else:
                if table1[keys]!=table2[keys]:
                    return False
        return True
    
    def subArrayContainsAnagram(self,str1,str2):
        length1=len(str1)
        length2=len(str2)
        front=0
        table1={}
        table2={}
        for i in str1:
            if i in table1:
                table1[i]+=1
            else:
                table1[i]=1
        for j in range(length1):
            if str2[j] in table2:
                table2[str2[j]]+=1
            else:
                table2[str2[j]]=1
        end=length1-1
        while True:
            if self.judge(table1, table2):
                return True
            else:
                end += 1
                if end == length2:
                    return False
                else:
                    if str2[end] in table2:
                        table2[str2[end]] += 1
                    else:
                        table2[str2[end]] = 1
                if table2[str2[front]]==1:
                    table2.pop(str2[front])
                else:
                    table2[str2[front]]-=1
                front+=1

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.