Permutation in String

 Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words,

one of the first string’s permutations is the substring of the second string.

For example:

Input: s1 = "ab" s2 = "eidbaooo"

Output: True

Explanation: s2 contains one permutation of s1 ("ba").

public class PermutationInString {

    public static void main(String[] args) {

        boolean bool = checkInclusion();

        System.out.println(bool);

    }

    private static boolean checkInclusion(){

        String str1 = "eidbaooo";

        String str2 = "ab";

        Map<Character, Integer> map2 = new HashMap<>();

        for(int i = 0;i<str2.length();i++){

            char ch = str2.charAt(i);

            map2.put(ch,map2.getOrDefault(ch,0)+1);

        }

        Map<Character, Integer> map1 = new HashMap<>();

        int i = -1;

        int j=-1;

        int desireCount = str2.length();

        int mCount = 0;

        boolean resultFlag= false;

        while (true){

            boolean f1 = false,f2 = false;

            while (i<str1.length()-1 && mCount<desireCount){

                f1= true;

                i++;

                char ch = str1.charAt(i);

                map1.put(ch,map1.getOrDefault(ch,0)+1);

                if(map1.getOrDefault(ch,0)<=map2.getOrDefault(ch,0)){

                    mCount++;

                }

                if(mCount==desireCount){

                    break;

                }

            }

            while (j<i && mCount==desireCount){

                f2 = true;

                j++;

                if(i+1-j==desireCount){ //check if size of string is same as desired count

                    //System.out.println("result");

                    resultFlag = true;

                    break;

                }

                char ch = str1.charAt(j);

                Integer val =map1.get(ch);

                if(val>1){

                    map1.put(ch,map1.get(ch)-1);

                }else{

                    map1.remove(ch);

                }

                if(map1.getOrDefault(ch,0)<map2.getOrDefault(ch,0)){

                    mCount--;

                }

                if(mCount<desireCount){

                    break;

                }

            }

            if(resultFlag){

                System.out.println("result found");

                break;

            }

            if(!f1 && !f2){

                System.out.println("result not found");

                break;

            }

        }

        if(resultFlag){

            //System.out.println("result found");

            return true;

        }else{

            //System.out.println("not found");

            return false;

        }

     //   return true;

    }

}

Result:true

Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in

complexity O(n).

For example, S = "ADOBECODEBANC", T = "ABC", Minimum window is "BANC". 

//we need to find smallest substring from str1 if all character of str2 available in substring

public class MinimumWindowSubstring {

    public static void main(String[] args) {

        String str1 = "dbaecbbabdcaafbddcabgba";

        String str2 = "abbcdc";

       // String str1 = "a";

        //String str2 = "aa";

        int i = -1;

        int j = -1;

        //preparing a frequncy map of string 2

        Map<Character,Integer> map2 = new HashMap<>();

        for(int k = 0;k<str2.length();k++){

            char ch = str2.charAt(k);

            map2.put(ch, map2.getOrDefault(ch,0)+1);

        }

        Map<Character,Integer> map1 = new HashMap<>();

        int mCount = 0;

        int desireCount = str2.length();

        String result = "";

        while (true){

            boolean f1 = false,f2 = false;

            //we need to run till my current count  less then desired count(str2 count)

            while (i<str1.length()-1 && mCount<desireCount ){

                i++;

                char ch = str1.charAt(i);

                map1.put(ch,map1.getOrDefault(ch,0)+1);

                if(map1.getOrDefault(ch,0)<=map2.getOrDefault(ch,0)){

                    mCount++;

                }

                 f1 = true;

            }

            //we need to run this till we are getting my current count equal to desired count

            while (j<i && mCount==desireCount) {

                f2 = true;

                j++;

                String potentialAns = str1.substring(j,i+1);

                if(result.length()==0 || potentialAns.length()<result.length()){

                    result = potentialAns;

                }

                char ch = str1.charAt(j);

                Integer val = map1.get(ch);

                if(val>1){

                    map1.put(ch,map1.get(ch)-1);

                }else{

                    map1.remove(ch);

                }

                if(map1.getOrDefault(ch,0)<map2.getOrDefault(ch,0)){

                    mCount--;

                }

                 f2 = true;

            }

            if(!f1 && !f2){

                break;

            }

        }

        System.out.println(result);

    }

}

Result: cbbabdc

Longest Substring with K Distinct Characters

 Given "abcadcacacaca" and 3, it returns "cadcacacaca".

public class LongestSubstringExactKDistinctElement {

    public static void main(String[] args) {

        String str = "aabcbcdbca";

        int i =-1;

        int j =-1;

        int length = 0;

        int k =2;

        Map<Character,Integer> map = new HashMap<>();

        while (true){

            boolean f1 = false,f2 = false;

            //acquire

            while (i<str.length()-1){

                f1 = true;

                i++;

                char ch = str.charAt(i);

                if(map.containsKey(ch)) {

                    map.put(ch, map.get(ch)+1);

                }else{

                    map.put(ch,1);

                }

                if(map.size()==k){

                    length = Math.max(length,i-j);

                }else if(map.size()>k){

                    break;

                }

            }

            //release

            while (j<i){

                f2 = true;

                j++;

                char ch = str.charAt(j);

                Integer val = map.get(ch);

                if(val==1){

                    map.remove(ch);

                }else{

                    map.put(ch,map.get(ch)-1);

                }

                if(map.size()==k){

                    Math.max(length,i-j);

                    break;

                }else if(map.size()>k){

                    continue;

                }

            }

            if(!f1 && !f2){

                break;

            }

        }

        System.out.println(length);

    }

}

Result: 4

Longest Substring with At Most K Distinct Characters

Given a string, find the longest substring that contains only two unique characters. For example, given "abcbbb-

bcccbdddadacb", the longest substring that contains 2 unique character is "bcbbbbcccb".

//maximum k distict allowed

public class LongestSubstringMostKDisinctChar {

    public static void main(String[] args) {

        String str = "ddacbbaccdedacebb";

        int i = -1;

        int j =-1;

        Map<Character, Integer> map = new HashMap<>();

        int length = 0;

        int k  = 3;

        while (true){

            boolean f1= false, f2 = false;

            //acquire

            while (i<str.length()-1){

                f1 = true;

                i++;

                char ch = str.charAt(i);

                if(map.containsKey(ch)){

                    map.put(ch,map.get(ch)+1);

                }else{

                    map.put(ch,1);

                }

                if(map.size()<=k){

                    length = Math.max(length,i-j);

                }else {

                    break;

                }

            }

            while (j<i){

                f2 = true;

                j++;

                char ch = str.charAt(j);

                Integer val = map.get(ch);

                if(val>1){

                    map.put(ch,map.get(ch)-1);

                }else{

                    map.remove(ch);

                }

                if(map.size()==k){

                    length = Math.max(length,i-j);

                    break;

                }

            }

            if(!f1 && !f2){

                break;

            }

            //release

        }

        System.out.println(length);

    }

}

Result: 7

Longest Substring Without Repeating Characters

 Given a string, find the length of the longest substring without repeating characters. For example, the longest

substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring

is "b", with the length of 1.

public class LongestSubstringWithoutRepeatingchar2 {

    public static void main(String[] args) {

        String str = "abcabcbd";

       // String str = "";

        int i = -1;

        int j = -1;

        Map<Character, Integer> map = new HashMap<>();

        int len = 0;

        while (true){

            boolean f1 = false, f2 = false;

            while (i<str.length()-1) {

                f1 = true;

                i++;

                char ch = str.charAt(i);

                if (map.containsKey(ch)) {

                    map.put(ch, map.get(ch) + 1);

                    break;

                } else {

                    map.put(ch, 1);

                    len = Math.max(len, i - j);

                }

            }

            while (j<i){

                f2 = true;

                j++;

                char ch = str.charAt(j);

                Integer val = map.get(ch);

                if(val>=2){

                    map.put(ch,map.get(ch)-1);

                    len = Math.max(len,i-j);

                    break;

                }else{

                    map.remove(ch);

                }

            }

            if(!f1 && !f2){

                break;

            }

        }

        System.out.println(len);

       // System.out.println(len);

    }

}

Result: 3