Short Permutation in a Long String


  • 0

    Click here to see the full article post


  • 0

    i impove the 4th solution

        public class Solution {
    	    public boolean checkInclusion(String s1, String s2) {
    	        int n = s1.length(), m = s2.length();
    	        int[] f = new int[26];
    	        for(int i = 0;i < n;i++){
    	        	f[s1.charAt(i)-'a']++;
    	        }
    	        int[] g = new int[26];
    	        for(int i = 0;i < m;i++){
    	        	g[s2.charAt(i)-'a']++;
    	        	if(i >= n){
    		        	g[s2.charAt(i-n)-'a']--;
    	        	}
    	        	if(Arrays.equals(f, g))return true;
    	        }
    	        return false;
    	    }
    	}
    

  • 0
    N

    Accepted Solution, different logic, no need to compare arrays or maps, just keeping track of length and move window to next possible character for substring, when new character is scanned

    public class Solution {
    public boolean checkInclusion(String s1, String s2) {
    int[] needToFind = new int[256];
    int[] hasFound = new int[256];

        int s1Len = s1.length();
        for (int i = 0; i < s1Len; i++) needToFind[s1.charAt(i)]++;
    
        for (int start=0,end = 0,len=0; start<s2.length() && end < s2.length(); end++) {
            char c = s2.charAt(end);
            if(needToFind[c]==0) //this character does not exist in original string, so we can scan from next character only and start will be next of this character
            {
                while(start<end) hasFound[s2.charAt(start++)]--;
                start = end+1;
                len=0;
            }
            else{
                    while (hasFound[c]==needToFind[c]){ //if increased frequency of character is encountered again we need to move window till that character is removed
                        hasFound[s2.charAt(start++)]--;
                        len--;
                    }
                hasFound[c]++;
                len++;
                if(len == s1Len) return true; //if length becomes same to s1 then s2 contains permutation of s1
            }
        }
        return false;
    }
    

    }


  • 0

    More simple Solution:

    public boolean checkInclusion(String s1, String s2) {
    int [] map = new int [256];
    for (char ch : s1.toCharArray()) map [ch] ++;
    for (int idx = 0, start = 0; idx < s2.length(); idx ++) {
    char ch = s2.charAt (idx);
    if (-- map [ch] < 0) while (map [ch] != 0) map [s2.charAt (start ++)] ++;
    else if (idx - start + 1 == s1.length()) return true;
    }
    return false;
    }


Log in to reply
 

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