Strings.txt

Solutions of these questions are either on GFG or LEETCODE 

---------------------------------------Strings-----------------------------------------
1. A Program to check if strings are rotations of each other or not
-> The idea is if the other string is rotation of main string then it must be a substring of the double times main string.               
                     str1 = "ABACD"
                     str2 = "CDABA"
     temp = str1.str1 = "ABACDABACD"
     Since str2 is a substring of temp, str1 and str2 are 
     rotations of each other.
Using KMP->O(n+m)


-----------------------------------------------------------------------------------
2. KMP (Knuth Morris Pratt algorithm)->T(n+m)->https://www.youtube.com/watch?v=V5-7GzOfADQ

	private static void KMPAlgo(String txt, String pat) {
		int m = txt.length();
		int n = pat.length();

		int[] lps = new int[n];
		computeLPS(n, pat, lps);
		int i = 0, j = 0;
		while (i < m) {
			if (pat.charAt(j) == txt.charAt(i)) {
				i++;
				j++;
			}
			if (j == n) {
				System.out.println("pattern found at idx->" + (i - j));
				j = lps[j - 1]; // for further pattern matching indexes if any.
			} else if (i < m && pat.charAt(j) != txt.charAt(i)) {
				if (j != 0) {
					j = lps[j - 1];
				} else {
					i = i + 1;
				}
			}
		}
	}
	private static void computeLPS(int n, String pat, int[] lps) {
		// also known as pie table
		int i = 1;
		int len = 0;
		lps[0] = 0;
		while (i < n) {
			if (pat.charAt(i) == pat.charAt(len)) {
				len++;
				lps[i] = len;
				i++;
			} else {
				if (len != 0) {
					// when the pattern breaks and len is also not at initial pos
					len = lps[len - 1];
				} else {
					lps[i] = len;
					i++;
				}
			}
		}
	}
-----------------------------------------------------------------------------------
3. Check if a string is a valid shuffle of two distinct strings
 s1 = "XY";
 s2 = "12";
   results->{"1XY2", "Y12X"};
first result is valid because the order is maintained while the other is not valid
public static void ValidShuffle(){
		String s1 = "xy";
		String s2 = "12";
		String res = "x21y";

		int l1 = s1.length();
		int l2 = s2.length();
		int lr = res.length();

		if ((l1 + l2) != lr) {
			System.out.println("Not Valid");
		} else {
			int i = 0, j = 0, k = 0;
			boolean flag = true;
			while (k < lr) {
				if (i < l1 && s1.charAt(i) == res.charAt(k)) {
					i++;
				} else if (j < l2 && s2.charAt(j) == res.charAt(k)) {
					j++;
				} else {
					flag = false;
					break;
				}
				k++;
			}
			if (flag) {
				System.out.println("Valid");
			} else {
				System.out.println("Not Valid");
		}
	}
} 
-----------------------------------------------------------------------------------
4. Count and say (recursive solution)  public String countAndSay(int n) {
    if(n==1) return "1";
    String ans = "1";
    for(int i=2; i<=n; i++){
        ans = f(ans);
    }
    return ans;
}

String f(String s){
    char ch = s.charAt(0);
    int count = 1;
    StringBuilder sb = new StringBuilder();
    for(int i=1; i<s.length(); i++){
        if(s.charAt(i) != ch){
            sb.append(count).append(ch);
            ch = s.charAt(i);
            count = 1;
        } else {
            count++;
        }
    }
    sb.append(count).append(ch);
    return sb.toString();
}
-----------------------------------------------------------------------------------
5. Longest Palindrome in a string ->T(N^2)
public static void main (String[] args) {
	Scanner scn = new Scanner(System.in);
     	int t = scn.nextInt();
		while (t-- > 0) {
			String str = scn.next();
			String s = null;
			String s1 = null;
			int count = 0;
			int maxc = Integer.MIN_VALUE;
			int n = str.length();

			// for odd length
			for (int axis = 0; axis < n; axis++) {
				count = 0;
				for (int orbit = 0; axis + orbit < n && axis - orbit >= 0; orbit++) {
					if (str.charAt(axis + orbit) == str.charAt(axis - orbit)) {
						count++;
						s1 = str.substring(axis - orbit, axis + orbit + 1);
					} else {
						break;
					}
				}
				if (count > maxc) {
					maxc = count;
					s = s1;
				}
			}

			// for even length
			for (double axis = 0.5; axis < n; axis++) {
				count = 1;
				for (double orbit = 0.5; axis + orbit < n && axis - orbit >= 0; orbit++) {
					if (str.charAt((int) (axis + orbit)) == str.charAt((int) (axis - orbit))) {
						count++;
						s1 = str.substring((int) (axis - orbit), (int)(axis + orbit + 1));
					} else {
						break;
					}
				}
				if (count > maxc) {
					maxc= count;
					s = s1;
				}
			}
			System.out.println(s);
		}
	}
-----------------------------------------------------------------------------------
6. Print all the subsequences of a string

private static void PrintSubsequences(String q, String ans) {
		if(q.length()==0) {
			System.out.println(ans);
			return;
		}
		
		char ch=q.charAt(0);
		String roq=q.substring(1);
		
		//not include
		PrintSubsequences(roq, ans);
		//include
		PrintSubsequences(roq, ans+ch);
	}
-----------------------------------------------------------------------------------
7. Permutations of a given string using backtracking
-> use   private static ArrayList<String> res;
->and after calling this FUNCTION->
Collections.sort(res);
System.out.println(res.toString().replace("[","").replace("]","").replace(",",""));
	private static void Permutations(int cs, int ts, HashMap<Character, Integer> fmap, String ans) {
		if (cs> ts) {
		  res.add(ans);
			return;
		}
		for (char ch : fmap.keySet()) {
			if (fmap.get(ch) > 0) {
				// backtrack
				fmap.put(ch, fmap.get(ch) - 1);
				Permutations(cs + 1, ts, fmap, ans + ch);
				fmap.put(ch, fmap.get(ch) + 1);
			}
		}
	}
-----------------------------------------------------------------------------------
8. Split the binary string into substrings with equal number of 0s and 1s
Approach->Just take 2 variables count1 and count0, traverse through the
string and whenever both counts become equal increase the main count 
after traversing if you found that both counts are not equal then return -1 
else return main count.
-----------------------------------------------------------------------------------
9. Next permutations 
->already done in arrays section.
-----------------------------------------------------------------------------------
10. Rabin karp ALgorithm->avg case O(n+m), worst case O(nm)

/ d is the number of characters in the input alphabet 
    public final static int d = 256; 
      
    /* pat -> pattern 
        txt -> text 
        q -> A prime number 
    */
    static void search(String pat, String txt, int q) 
    { 
        int M = pat.length(); 
        int N = txt.length(); 
        int i, j; 
        int p = 0; // hash value for pattern 
        int t = 0; // hash value for txt 
        int h = 1; 
      
        // The value of h would be "pow(d, M-1)%q" 
        for (i = 0; i < M-1; i++) 
            h = (h*d)%q; 
      
        // Calculate the hash value of pattern and first 
        // window of text 
        for (i = 0; i < M; i++) 
        { 
            p = (d*p + pat.charAt(i))%q; 
            t = (d*t + txt.charAt(i))%q; 
        } 
      
        // Slide the pattern over text one by one 
        for (i = 0; i <= N - M; i++) 
        { 
      
            // Check the hash values of current window of text 
            // and pattern. If the hash values match then only 
            // check for characters on by one 
            if ( p == t ) 
            { 
                /* Check for characters one by one */
                for (j = 0; j < M; j++) 
                { 
                    if (txt.charAt(i+j) != pat.charAt(j)) 
                        break; 
                } 
      
                // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1] 
                if (j == M) 
                    System.out.println("Pattern found at index " + i); 
            } 
      
            // Calculate hash value for next window of text: Remove 
            // leading digit, add trailing digit 
            if ( i < N-M ) 
            { 
                t = (d*(t - txt.charAt(i)*h) + txt.charAt(i+M))%q; 
      
                // We might get negative value of t, converting it 
                // to positive 
                if (t < 0) 
                t = (t + q); 
            } 
        } 
    } 
-----------------------------------------------------------------------------------
11. Convert a Sentence into its equivalent mobile numeric keypad sequence.

 String arr[] = {"2","22","222", 
                        "3","33","333", 
                        "4","44","444", 
                        "5","55","555", 
                        "6","66","666", 
                        "7","77","777","7777", 
                        "8","88","888", 
                        "9","99","999","9999"
                    }; 
  
 static String printSequence(String arr[], 
                               String input) 
    { 
        String output = ""; 
      
        // length of input string 
        int n = input.length(); 
        for (int i = 0; i < n; i++) 
        { 
            // Checking for space 
            if (input.charAt(i) == ' ') 
                output = output + "0"; 
      
            else
            { 
                // Calculating index for each  
                // character 
                int position = input.charAt(i) - 'A'; 
                output = output + arr[position]; 
            } 
        } 
      
        // Output sequence 
        return output; 
    } 
-----------------------------------------------------------------------------------
12. Count the reversals

public static void main (String[] args) {
		int t =scn.nextInt();
		
		while(t-->0){
		    String str=scn.next();
		  
		  if(str.length()%2!=0){
		      System.out.println("-1");
		  }else{
		    int b=0;
		    int c=0;
            for(int i=0;i<str.length();i++){
                int temp=str.charAt(i);
                if(temp=='{'){
                    b++;
                }
                if(temp=='}'){
                    b--;
                }
                
                if(b<0){
                    b=1;
                    c++;
                }
            }
            
            //in case when b is not zero and   {{{{   such thing happens
            c=c+b/2;
            
		   System.out.println(c);   
		  }	    
		}
	}

-----------------------------------------------------------------------------------
13. Find the string in grid ->O(m*n*8*l).
  UP_LEFT(-1,-1), UP(-1,0), UP_RIGHT(-1,1), RIGHT(0,1), DOWN_RIGHT(1,1), DOWN(1,0), DOWN_LEFT(1,-1), LEFT(0,-1).       

	public static void FindStringInGrid(char[][]grid,int n,int m,String word){
	    
	    boolean found=false;
	    int count=0;
	     for(int row=0;row<n;row++){
            for(int col=0;col<m;col++){
               found=Find(grid,row,col,word,n,m);
               if(found){
                   if(count==0){
                        System.out.print(row+" "+col+",");
                   }else{
                       System.out.print(" "+row+" "+col+",");
                   }
                   count++;
               }
            }
        }
        if(count==0){
            System.out.print("-1");
        }
	}
	public static boolean Find(char[][]grid,int R,int C,String word,int n,int m){
	    int[]x={-1,-1,-1,0,1,1,1,0}; //x-axis
	    int[]y={-1,0,1,1,1,0,-1,-1}; //y-axis
	    int row_d;
	    int col_d;
	    if(grid[R][C]!=word.charAt(0)){
	        return false;
	    }
	    //so we skip the first character as we have checked it.
	    // checking in all 8 directions
	    for(int dir=0;dir<8;dir++){
	        row_d=R+x[dir];
	        col_d=C+y[dir];
	        int noc;// number of characters of given word count;
	        for(noc=1;noc<word.length();noc++){
	            if(row_d<0||row_d>=n||col_d<0||col_d>=m){
	                break;
	            }
	            if(word.charAt(noc)!=grid[row_d][col_d]){
	                break;
	            }
	            row_d+=x[dir]; //going through that direction
	            col_d+=y[dir]; //going through that direction 
	        }
	        if(noc==word.length()){
	            return true;
	        }
	    } 
	    return false;
	}
-----------------------------------------------------------------------------------
14. Boyer Moore Algorithm for pattern Matching- Bad Character Heuristic
-----------------------------------------------------------------------------------
15. Roman Number to Integers.

public static int romanToDecimal(String str) {
		int ans = 0;
		for (int i = 0; i < str.length() - 1; i++) {
			char a = str.charAt(i);
			char b = str.charAt(i + 1);
			if (getval(a) < getval(b)) {
				ans -= getval(a);
			} else {
				ans += getval(a);
			}
		}
		ans += getval(str.charAt(str.length() - 1));
		return ans;
	}
	static int getval(char ch) {
		if (ch == 'I') {
			return 1;
		}
		if (ch == 'V') {
			return 5;
		}
		if (ch == 'X') {
			return 10;
		}
		if (ch == 'L') {
			return 50;
		}
		if (ch == 'C') {
			return 100;
		}
		if (ch == 'D') {
			return 500;
		}
		if (ch == 'M') {
			return 1000;
		}
		return 0;
	}
-----------------------------------------------------------------------------------
16. Longest Common prefix
 public String longestCommonPrefix(String[] strs) {
        if(strs.length<1){ //as we need atleast two characters to compare.
            return "";
        }
        int idx=0;
        String res="";
        mainLoop:while(idx<strs[0].length()){
            char ch=strs[0].charAt(idx);
            for(int i=1;i<strs.length;i++){
                if(idx>=strs[i].length()||strs[i].charAt(idx)!=ch){  //here in case idx>=so and so  equal sign because if it will equal to some 	length then it means it crosses the index bound of that string.
                    break mainLoop;
                }
            }
            res+=ch;
            idx++;
        }
        return res;
    }
-----------------------------------------------------------------------------------
17. Min number of flips required (010101  ||  101010) just like this 
"001"->1 flip required,    "001010111"->2 flips   
public int minFlips(String s) {
                                      int mn1=0;
		    if(s.charAt(0)=='0'){
		            for(int i=0;i<s.length();i++){
		                char temp=s.charAt(i);
		                if((i%2==0 && temp=='1')||(i%2!=0 && temp=='0')){
		                    mn1++;
		                }
		            }
		    }else{
		       for(int i=0;i<s.length();i++){
		                char temp=s.charAt(i);
		                if((i%2==0 && temp=='0')||(i%2!=0 && temp=='1')){
		                    mn1++;
		                }
		            } 
		       }
		       int mn2=0;
		       if(s.charAt(0)=='1'){
		            for(int i=0;i<s.length();i++){
		                char temp=s.charAt(i);
		                if((i%2==0 && temp=='1')||(i%2!=0 && temp=='0')){
		                    mn2++;
		                }
		            }
		    }else{
		       for(int i=0;i<s.length();i++){
		                char temp=s.charAt(i);
		                if((i%2==0 && temp=='0')||(i%2!=0 && temp=='1')){
		                    mn2++;
		                }
		            } 
		       }
		       return Math.min(mn1,mn2);
    }
-----------------------------------------------------------------------------------
18. Second most repeated string in a sequence
Approach->Took a hashmap find the string having most frequency, then set those frequencies to 0, again find the string having highest freq which was ealier second highest.
-----------------------------------------------------------------------------------
19. Minimum swaps bracket balancing

static long swapCount(String s) 
	{
		char[] chars = s.toCharArray();
		
		// stores total number of Left and Right 
		// brackets encountered
		int countLeft = 0, countRight = 0; 
				// swap stores the number of swaps required
		//imbalance maintains the number of imbalance pair
		int swap = 0 , imbalance = 0; 
		
		for(int i =0; i< chars.length; i++) 
		{
			if(chars[i] == '[') 
			{
				// increment count of Left bracket
				countLeft++; 
				if(imbalance > 0) 
				{
					// swaps count is last swap count + total 
					// number imbalanced brackets‍
					swap += imbalance; 
					// imbalance decremented by 1 as it solved
					// only one imbalance of Left and Right
					imbalance--;	 
				}
			} else if(chars[i] == ']' ) 
			{
				// increment count of Right bracket
				countRight++; 
				// imbalance is reset to current difference 
				// between Left and Right brackets
				imbalance = (countRight-countLeft); 
			}
		}
		return swap;
	}
-----------------------------------------------------------------------------------
20. Smallest distinct window -> o(n) ,S(n)
“aabcbcdbca” -> "dcba"
"GEEKSGEEKSFOR"->"GEEKSFOR"
 public static String findSubString(String str) {

		HashMap<Character, Integer> map = CharMap(str);
		Set<Character> set = new HashSet<Character>();

		int i = 0;
		int j = -1;
		int len = Integer.MAX_VALUE;
		String s = "";
		while (j < str.length()) {
			if (set.size() == map.size()) {

				if (len > j - i) {
					len = j - i;
					s = str.substring(i, j + 1);
				}
				char c = str.charAt(i);
				if (map.get(c) > 1) {
					map.put(c, map.get(c) - 1);
					i++;
				} else {
					map.put(c, 0);
					i++;
					set.remove(c);
				}
				
			} else {
				j++;
				if (j < str.length()) {
					char temp = str.charAt(j);
					set.add(temp);
					map.put(temp, map.get(temp) + 1);
				}
			}
		}
		return s;
	}

	public static HashMap<Character, Integer> CharMap(String str) {
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		for (int i = 0; i < str.length(); i++) {
			char temp = str.charAt(i);
			map.put(temp, 0);
		}

		return map;
	}

-----------------------------------------------------------------------------------
21. Smallest window in a string containing all the characters of another string
S = "timetopractice"
P = "toc"
output->toprac
 public static String smallestWindow(String s, String p){
           String ans="";
        
        HashMap<Character,Integer>map2=new HashMap<>();
        for(int i=0;i<p.length();i++){
            char ch=p.charAt(i);
            map2.put(ch,map2.getOrDefault(ch,0)+1);
        }
        
        int mcn=0;//match count 
        int dmcn=p.length(); //desired match count
        int i=-1;
        int j=-1;
        HashMap<Character,Integer>map1=new HashMap<>();
        
        while(true){
            boolean flag1=false;
            boolean flag2=false;
            
            //acquire
            //i<s.length()-1 not i<s.length() because we increment i then access it..
            while(i<s.length()-1 && mcn<dmcn){
                i++;
                char ch=s.charAt(i);
                map1.put(ch,map1.getOrDefault(ch,0)+1);
                
                if(map1.getOrDefault(ch,0)<=map2.getOrDefault(ch,0))
                {
                    mcn++;
                }
                flag1=true;
                
            }
            
            //collect answers and release
            while(j<i && mcn==dmcn){
                //pans->potential ans
                String pans=s.substring(j+1,i+1);   //took from j+1 because jth character is already released
                if(ans.length()==0||ans.length()>pans.length()){
                    ans=pans;
                }
                j++;
                char ch=s.charAt(j);
                if(map1.get(ch)==1){
                    map1.remove(ch);
                }else{
                    map1.put(ch,map1.get(ch)-1);
                }
                if(map1.getOrDefault(ch,0)<map2.getOrDefault(ch,0)){
                    mcn--;
                }
                flag2=true;
            }
            if(!flag1 && !flag2){
                break;
            }
            
        }
        if(ans.length()==0){
            return "-1";
        }
        return ans;   
    }
-----------------------------------------------------------------------------------
23. Print Anagrams Together 
Anagrams means having same frequency map

  public List<List<String>> Anagrams(String[] string_list) {
      HashMap<HashMap<Character,Integer>,ArrayList<String>>bmap=new HashMap<>();
	     List<List<String>>ans=new ArrayList<>();
	     
	     for(String strs:string_list){
	         HashMap<Character,Integer>fmap=new HashMap<>();
	         for(int i=0;i<strs.length();i++){
	             char ch=strs.charAt(i);
	             fmap.put(ch,fmap.getOrDefault(ch,0)+1);
	         }
	    
	        if(!bmap.containsKey(fmap)){
	            List<String> li =new ArrayList<>();
	            li.add(strs);
	            bmap.put(fmap,(ArrayList<String>) li);
	        } else{
	            List<String>lb=bmap.get(fmap);
	            lb.add(strs);
	        }    
	     }
	     
	        for(List<String> res:bmap.values()){
	            ans.add(res);
	        }
	        return ans;
    }
-----------------------------------------------------------------------------------
24. Minimum characters to be added at front to make the string palindrome
Approach 1-> check the string for palindrome if not delete the last character,  then again check for palindrom until str.length()>0
Approach 2-> lps array
For string = AACECAAAA
Concatenated String = AACECAAAA$AAAACECAA
LPS array will be {0, 1, 0, 0, 0, 1, 2, 2, 2, 
                   0, 1, 2, 2, 2, 3, 4, 5, 6, 7}
Here we are only interested in the last value of this lps array because it shows us the largest suffix of the reversed string that matches the prefix of the original string i.e these many characters already satisfy the palindrome property. Finally minimum number of character needed to make the string a palindrome is length of the input string minus last entry of our lps array. 

public static int getMinCharToAddedToMakeStringPalin(String str) {
		StringBuilder s = new StringBuilder();
		s.append(str);

		// Get concatenation of string, special character
		// and reverse string
		String rev = s.reverse().toString();
		s.reverse().append("$").append(rev);
		System.out.println(s);

		// Get LPS array of this concatenated string
		int lps[] = computeLPSArray(s.toString());
		return str.length() - lps[s.length() - 1];
	}
-----------------------------------------------------------------------------------
25. Rearrange characters in a string such that no two adjacent are same
public String reorganizeString(String S) {
        HashMap<Character,Integer>map=new HashMap<>();
        
        for(char ch:S.toCharArray()){
        map.put(ch,map.getOrDefault(ch,0)+1);    
        }
        
        //used lambda as comparator 
        PriorityQueue<Character>hp=new PriorityQueue<>((a,b)->map.get(b)-map.get(a));
        hp.addAll(map.keySet());
        
        StringBuilder sb= new StringBuilder();
        
        while(hp.size()>1){
            char first=hp.remove();
            char second=hp.remove();
            
            sb.append(first);
            sb.append(second);
            
            map.put(first,map.get(first)-1);
            map.put(second,map.get(second)-1);
            
            if(map.get(first)>0){
                hp.add(first);
            }
            if(map.get(second)>0){
                hp.add(second);
            }
        }
        
        if(hp.size()!=0){
            char last=hp.remove();
            if(map.get(last)>1){
                return "";
            }else{
                sb.append(last);
            }
        }
        return sb.toString();        
        
        }
-----------------------------------------------------------------------------------
26. Function to find Number of customers who could not get a computer
"ABBAJJKZKZ"->0
"GACCBDDBAGEE"->1
"ABCABCDEED"->3

private static int runCustomerSimulation(int noc, char[] crr) {
		//noc-> number of computers
		int didnotget = 0;
		int occupied = 0;
		int[] visited = new int[26]; 

		for (int i = 0; i < crr.length; i++) {
			if(visited[crr[i]-'A']==0 && occupied<noc) {
				visited[crr[i]-'A']=1;
				occupied++;
			}else if(visited[crr[i]-'A']==1 && occupied<=noc) {
				occupied--;
				visited[crr[i]-'A']=0;
			}else {
				didnotget++;
			}
		}

		return didnotget/2;
	}
-----------------------------------------------------------------------------------
27. Isomorphic strings
xxy-aab->true , xxy-abc->false
 public static boolean areIsomorphic(String str1,String str2)
    {
       if(str1.length()!=str2.length()){
           return false;
       }
       
       char[]ch1=new char[256];
       char[]ch2=new char[256];
        for(int i=0;i<str1.length();i++){
            char c1=str1.charAt(i);
            char c2=str2.charAt(i);
            if(ch1[(int)(c1)]!=ch2[(int)(c2)]){
                return false;
            }else{
                ch1[c1]++;
                ch2[c2]++;
            }
           
        }
        return true;
    }
-----------------------------------------------------------------------------------
28. Recursively print all sentences that can be formed from list of word lists
r=0,str=2d character array but with variable length of column, sen =empty sentence string
	public static void print(String[][] str, String sen, int r) {
		if (str.length == r) {
			System.out.println(sen);
			return;
		}

		for (int i = 0; i < str[r].length; i++) {
			if(str[r][i]!="")
			print(str, sen + " " + str[r][i], r + 1);
		}
	}
-----------------------------------------------------------------------------------
29.  Transform One String to Another using Minimum Number of Given Operation

 public static int minOps(String A, String B) 
    { 
          
        // This parts checks whether conversion is 
        // possible or not 
        if(A.length() != B.length()) 
            return -1; 
          
        int i, j, res = 0; 
        int count [] = new int [256]; 
          
        // count characters in A 
          
        // subtract count for every character in B 
        for(i = 0; i < A.length(); i++) 
        { 
            count[A.charAt(i)]++; 
            count[B.charAt(i)]--; 
        } 
          
        // Check if all counts become 0 
        for(i = 0; i < 256; i++) 
            if(count[i] != 0) 
                return -1; 
          
        i = A.length() - 1; 
        j = B.length() - 1; 
  
        while(i >= 0) 
        { 
            // If there is a mismatch, then  
            // keep incrementing result 'res' 
            // until B[j] is not found in A[0..i] 
            if(A.charAt(i) != B.charAt(j)) 
                res++; 
            else
                j--; 
            i--;          
        } 
        return res;      
    } 
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------