Permutation of string as substring of another (JAVA)


  • 0
    J

    Given a string A and another string B. Find whether any permutation of B exists as a substring of A. Return starting index of B in A.

    For example,
    if A = "encyclopedia"
    if B="dep" then return index 7 as ped is a permutation of dep and ped is a substring of A.

    Corner Condition:

    1. May be String A or B NULL.
    2. May be length of substring is greater than main string.

    Time Complexity: O(n)
    Space Complexity: O(1)

    int permutationOfStringAsSubstringOAnotherString(String mainStr, String subStr){
    	if(mainStr == null || subStr==null || subStr.length() > mainStr.length())
    		return -1;
    	
    	int lenSubStr = subStr.length(), lenMainStr = mainStr.length();
    	char alphaMainS[] = new char[26], alphaSubS[] = new char[26];
    	for(int i=0; i < lenSubStr; i++){
    		alphaMainS[mainStr.charAt(i) - 'a'] +=1;
    		 alphaSubS[subStr.charAt(i) - 'a'] +=1;
    	}
    	
    	for(int i=lenSubStr; i < lenMainStr; i++){
    		if(String.valueOf(alphaMainS).compareTo(String.valueOf(alphaSubS)) == 0){
    			return i - lenSubStr;
    		}
    		alphaMainS[mainStr.charAt(i) - 'a'] +=1;
    		alphaMainS[mainStr.charAt(i-lenSubStr) - 'a'] -=1;
    	}
    	
    	if(String.valueOf(alphaMainS).compareTo(String.valueOf(alphaSubS)) == 0){
    		return lenMainStr - lenSubStr;
    	}		
    	return -1;
    }
    

Log in to reply
 

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