Sub Array Contains Anagram


  • 2
    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?


  • 1
    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

  • 0
    K
    #Another way to solve this problem
    
    def anagram_check(str1, str2):
        
        #if str2 is in str1 it is anagram return true 'GLE' =>Google
        if str2 in str1:
            return True
        
        # get all the permutations and check it in given string
        p_codes = permute(str2)
        
        for i  in range(len(p_codes)):
            if ''.join(p_codes[i]) in str1:
                return True
        return False
        
        
    #find the combinations of subsstring check them in str1 (GLE => GLE, GEL, LEG, LGE, EGL, ELG)
    # thanks to https://leetcode.com/problems/permutations/discuss/
    
    def permute(nums):
        return nums and [p[:i] + [nums[0]] + p[i:]
                         for p in permute(nums[1:])
                         for i in range(len(nums))] or [[]]
        
        
        
        
        
    anagram_check("Google","geo")
    

  • 0
    E

    @ryanwww said in Sub Array Contains Anagram:

    O(N) with slide window and hash

    O(length1*length2)


  • 0
    A

    @sach323 can we break when the first minlen==pattern.length?


  • 0
    S

    @abhishek140 Yes you can. I modified this program from Min Window substring where you have to traverse whole string to make sure you find min len but in this case as soon as pattern matches you can break


  • 0

    from collections import Counter
    def is_anagram(str1,str2):
    return Counter(str1) == Counter(str2)


  • 0
    S

    @sach323 said in Sub Array Contains Anagram:

    counter--;

    bool subStringAnagram(string pattern, string str){

    unordered_map<char,int> hashMap;
    unordered_map<char,int> winMap;
    for (auto c: pattern){
        ++hashMap[c];
    }
    int numChar = hashMap.size();
    int start = 0;
    winMap = hashMap;
    int charCount = 0;
    
    for (int i = 0; i < str.size(); ++i){
        char c = str[i];
        if(hashMap.count(c) == 0){
            charCount = 0;
        }
        else{
            if(charCount == 0) {
                start = i;
                winMap = hashMap;
            }
            /* Cannot take this character and start moving from start index till we find char C */
            if(winMap[c] == 0){
                while(start < i){
                    if(str[start++] == c){
                        break;
                    }
                }
                if(start == i){
                    --i; charCount = 0;
                }
            }
            else{
                if(--winMap[c] == 0){
                    if(++charCount == numChar){
                        return true;
                    }
                }
            }
        }
    }
    return false;
    

    }


  • 0
    S

    @ebracho I know that you could do a hash of character. Lets say A1A2A3 and B1B2B3 are two different words that has different characters, but lets assume their hashes when summed together would result in the same value. Then this solution would break. So what would be a good approach to hash the words ( characters ) ?


  • 0
    S

    Here is my solution in R

    library(hashmap)
    
    SubstringAnagram=function(subString, fullString)
    {
      subLetter=table(unlist(strsplit(subString,"")))
      MapTable = hashmap(names(subLetter),subLetter)
      i=1
      while(i<=nchar(fullString))
      {
        if(is.na(MapTable$find(substr(fullString,i,i)))==FALSE)
          {
            tempTable=clone(MapTable)
            j=i
            while(is.na(tempTable$find(substr(fullString,j,j)))==FALSE &&
                  tempTable$find(substr(fullString,j,j))>0
                  && j<=nchar(fullString))
            {
              tempTable$insert(substr(fullString,j,j),tempTable$find(substr(fullString,j,j))-1)
              j=j+1
            }
            if(length(unique(tempTable$values()))==1 && unique(tempTable$values())[1]==0)
              return("YES")
        }
        i=i+1
      }
      return("NO")
    
    }
    
    
    SubstringAnagram("ogo","google")
    

Log in to reply
 

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