Strings - I

Strings - I

Input: s = "(()())(())"
Output: "()()()"
Explanation: 
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".

Algorithm:

Input : A parenthesis String

Output : String with eliminated outermost parenthesis

Steps:

1 ] Initialize an empty StringBuilder to store the final resulting string.

Initialize the depth variable to 0.

2 ] Run a for loop for checking each character in the parenthesis string.

if we encounter “ ( “ character :

check if depth > 0 : append the character in the StringBuilder

increment the depth count.

else if we encounter “ ) “ character :

decrement the depth count.

check if depth > 0 : append the character in the StringBuilder

3 ] return the StringBuilder in string format.

Java code:


public class RemoveOutermostParenthesis{
      public static void main(String[] args){
           String st = "(()())(())";
           System.out.println(solution(st));
      }

      public static String solution(String s){
           StringBuilder result = new StringBuilder();
           int depth = 0;

           for (char c : s.toCharArray()){
                if( c == '(' ){
                     if( depth > 0 ){
                         result.append(c);
                     } 
                     depth ++;
                } else if ( c == ')' ){
                     depth --;
                     if( depth > 0 ){
                          result.append(c);
                     }
                }
           }

           return result.toString();
      }

}

Time Complexity : O(N)

Space Complexity : O(N)

Input: num = "52"
Output: "5"
Explanation: The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.

Algorithm :

Input : A string of numbers

Output : A substring containing odd number

Steps :

1 ] Use for loop to iterate upon each digit of the string from the end.

2 ] Check if the current digit is divisible by 2 :

If yes select the substring between the range of the starting digit to the current digit.

3 ] return the substring

public class LargestOddNumber{
     public static void main(String[] args){
           String num = "4306";
           System.out.println(solution(num));
     }

     public static String solution(String st){
          for(int i = st.length() - 1; i >= 0; i --){
               if(Character.getNumericValue(st.charAt(i)) % 2 != 0){
                       return st.substring(0, i + 1);
               }
          }

          return " ";
     }
}

Time Complexity : O(N)

Space Complexity : O(1)

Input: s = "egg", t = "add"

Output: true

Algorithm:

Input : Two input strings

Output : Boolean value indicating is isomorphic or not

Steps :

1 ] Check the length of the two input strings. If length is different return false.

2 ] Initialize two empty Hashmaps.

3 ] Run a for loop from 0 to length of any string.

4 ] For each index of the for loop get a character at the index from both the strings.

5 ] Check for mapping between (ch1 → ch2) :

if ch1 exists in the map but it is not mapped to ch2 : return false

else if ch1 does not exist create a mapping (ch1 → ch2)

6 ] Check for mapping between (ch2 → ch1):

if ch2 exists in the map but it is not mapped to ch1 : return false

else if ch2 does not exist create a mapping (ch2 → ch1)

7 ] Return true

Java code :

import java.util.HashMap;

public class IsomorphicStrings{
     public static void main(String[] args){
        String str1 = "egg";
        String str2 = "add";
        System.out.println(solution(str1, str2));

     }

     public static boolean solution(String s1, String s2){
          if(s1.length() != s2.length()){
              return false;
          }

          Hashmap<Character, Character> map1 = new Hashmap<>();
          Hashmap<Character, Character> map2 = new Hashmap<>();

          for(int i = 0; i < s1.length(); i++){
               char ch1 = s1.charAt(i);
               char ch2 = s2.charAt(i);

               if(map1.containsKey(ch1)){
                    if(map1.get(ch1) != ch2){
                         return false;
                    }
               } else {
                    map1.put(ch1, ch2);
               }

               if(map2.containsKey(ch2)){
                    if(map2.get(ch2) != ch1){
                         return true;
                    }
               } else {
                    map2.put(ch2, ch1);
               }
          }

          return true;
     }

}

Time Complexity : O(N)

Space Complexity : O(1)

Input: strs = ["flower","flow","flight"]
Output: "fl"

Algorithm :

Input : Array of strings

Output : Prefix string

Steps :

1 ] First check if the string array is empty or length of the array is 0 then return an empty string.

2 ] Consider the first string element in the array as the prefix.

3 ] Use a for loop to iterate over each string in the array from position 1 to the last index.

If the current string does not start with the prefix characters :

reduce the prefix string by one character.

4 ] return the prefix string

public class LargestCommonPrefix{
    public static void main(String[] args){
          String[] str = {"flower", "flight", "flow"};
          System.out.println(solution(str));
    }

    public static String solution(String[] str){
          if(str == null || str.length == 0){
                return " ";
          } 

          String prefix = str[0];

          for(int i = 1; i < str.length; i++){
                while(str[i].indexOf(prefix) != 0){
                       prefix = prefix.substring(0, prefix.length() - 1);

                       if(prefix.isEmpty()){
                             return " ";
                       }
                }
          }

          return prefix;
    }
}

Time Complexity : O(M * N) [m = length of shortest string, n = number of strings in array]

Space Complexity : O(1)

Input: s = "anagram", t = "nagaram"

Output: true

Algorithm :

Input : Two strings

Output : Boolean output indicating anagram or not.

Steps :

1 ] Check the lengths of the two string if they are not equal return false.

2 ] Create an empty array to track the count of each alphabet in the strings.

3 ] For the first string calculate the index of each alphabet and increment the count in the empty array.

4 ] For the second string calculate the index of each alphabet and decrement the count in the array.

If the count goes lower than 0 : return false

5 ] return true

public class ValidAnagrams{
    public static void main(String[] args){
         String st1 = "anaragm";
         String st2 = "nagaram";
         System.out.println(solution(st1, st2));
    }

    public static boolean solution(String st1, String st2){
         if(st1.length() != st2.length()){
             return false;
         }

         int[] CharCount = new int[26];

         for(char c : st1.toCharArray()){
              CharCount[c - 'a'] ++;
         }

         for(char c : st2.toCharArray()){
              CharCount[c - 'a'] --;

              if(CharCount[c - 'a'] < 0){
                   return false;
              }
         }

         return true;
    }
}

Time Complexity : O(N)

Space Complexity : O(1)

Subscribe to our newsletter

Read articles from Reuben's blog directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Did you find this article valuable?

Support Reuben's blog by becoming a sponsor. Any amount is appreciated!