Partition labels

Given a string S, partition the string into maximum possible partitions so that each letter appears in at most one part, and return a list of integers containing the size of each partition.
For example:

Input: 
S = "ababcbacadefegdehijhklij"
Output:
[9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into fewer parts.

This problem is commonly asked in Amazon interviews.

Thought process to partition string in labels

Fundamental idea is that if two instances of characters should be in the same partition. So, we start with the first character and see at what point we can finish the partition. The earliest we can do is at the last instance of this character.
What if we find a character between the first character and the last instance of it? In this case, we increase the length of the partition. Why? If we do not increase the partition, the new character ends up into two partitions, which violates the constraint of the problem.

If we have gone through all the characters between the start of partition and maximum of the last instance of characters, we can close the partition and start a new one.

Let’s take an example and see how it works. Start with the first character of the string and find the last instance of that character, in this case, it is a
partition labels

Go through all the characters until the last instance, if the last instance of any of the characters is greater than the current last instance, expand the partition to include new last instance. In this example, none of the characters have the last index beyond the last index of a

Once, we reach the last index, we can close the current partition and start a new one. Find the last instance of the first character of the new partition.

amazon interview question partition labels

Go though the characters in between. In this example, character e has last instance greater than current one, so we update the partition till e.

There is no character in between with the last instance greater than the last instance of e, so we close the partition there and start the next one from the next character in the string which is h

Next character i will expand the partition to index 22 and next to next character j will push it to 23. There is no other character that has the last occurrence after that index. Hence, we would close the partition there.
partitions

Whenever we are closing the partition, we would add the length of that partition end – start + 1 in a list to return.

Partition labels implementation

class Solution {
    public List<Integer> partitionLabels(String S) {
        
        Map<Character, Integer> map = new HashMap<>(); 
        
        //Get the last index the character.
        for(int i=0; i< S.length(); i++){
            map.put(S.charAt(i), i);
        }
        
        int last = 0;
        int start = 0;
        
        List<Integer> list = new ArrayList<>();
        for(int i=0; i< S.length(); i++){  
            
            last = Math.max(last, map.get(S.charAt(i)));
            if(last == i){
                list.add(last - start + 1);
                start = last + 1;
            }
        }
        
        return list;
    }
}

The time complexity of implementation is O(n), however, we are scanning the string twice. We also need constant space. Do not get confused with map, the maximum size of the map is bound by 52 (upper and lower case characters) irrespective of the size of the string.

Please share if there is something wrong or missing.

Palindrome anagram

Given a string, find out if any anagram of a given string is a palindrome. For example, “AABBC” has an anagram “ABCBA” which is a palindrome.
The brute force solution will be to find all anagrams of string and then check each one if that is a palindrome. For N character long string, we will have n! anagrams, and checking each one of that for palindrome will be a computation-intensive task, so not a good solution.

What is required for a string to be palindrome string? We need first half of the string to contain the same characters as the second half. In the case of odd length string, we can safely ignore the middle character.
In other terms, each character should occur even a number of times except one which is a middle character that may occur an odd number of times. Best way to check if the character occurs even number of times is to increment to count when it is zero and decrement when it is 1.If at the end we have count corresponding to that character as zero, that means we have even number of occurrence of this character, if not then we have an odd number of occurrence.

Extending the same idea from the previous post: we will be using a hash table and increment- decrement the corresponding count of character in the hash. In the end, we will sum the array and if the sum of the array is greater than 1, then we cannot have any anagram which will be palindrome else at least anagram of the string will be a palindrome.

The complexity of above code is O(N) with a constant amount of memory required.

Anagrams : Find if two strings are anagrams

Check if strings are anagram

Given two strings, find out if they are anagrams of each other. Strings are said to be anagrams if they have same characters but in different order.For example, abcd and dcba are anagrams.

Analysis

It’s actually a simple problem, we need to just check if both the strings contain same characters. 
First approach will be to sort both the string and compare if they are same. While sorting all the characters will come in lexicographical order and string with same characters will have same order of characters.
Best we can achieve using sort is O(N log N).
Can we do better? We have to keep track of character in one string in another. So if we find what all characters (count of each character) are there in first string, we can easily do that using hash table and compare with characters (count again) present in second string. If both the hash tables are equal, we can say that strings are anagrams.
Here we are using two hash tables. We can do away with on hash table. How?
While traversing the first string we will increment the count against character. While traversing the second string, we will decrement the count against character in the same hash table. If at any time if count of any character goes less than zero, it means, character is present in second string but not in first, so we can say strings are not anagrams.
If we finish complete scanning of second string, we return true.
To avoid check the hash table at the end for non zero count, we can first have a check on length of two strings, if lengths are not equal, straightforwardly say non anagrams. (Think how it avoids check of non zero count at the end :))

Code to find if strings are anagrams

Complexity Analysis

Complexity of algorithm to identify to strings as anagrams is O(N) where N is length of string.

Convert excel column to equivalent number

Convert excel column to equivalent number

Every column is assigned a value, A =1 , B=2 … and Z= 26. Again AA = 27, AB = 28…. and AZ = 52. Given a string S, find out the equivalent number. For example for AAA it will be 703.

This problem has simple solution. We just need to come up with the mathematical formula for it. So let’s work out some examples so that we can identify some pattern and then figure out formula. A  = 1 = 1 * (26 ^0) AB = 2 + 26 ^1 =  28 AAB = 2 + 26^1 + 26^2 = 704  B  = 2 = 2 * (26 ^0) BB = 2 + 2 * (26^1) =  54 ABB = 2 + 2* (26^1) + 1 *( 26^2) = 730 C = 3  = 3 * (26 ^0)  AC  = 3 * (26^0) + 1 * (26^1) = 29 ACC = 3 * (26^0) + 3 * (26^1) + 1 * (26^2)=757

Do you see some pattern?  Yes, we need to get the power of 26 based on the place the character is in string , starting from right hand side. For example, in ABB, we took (26^2) because A is at second position from the right side, starting from zero. What else? We multiply that power to the value assigned to that character. For example, for C we multiply with 3. Value of single character can be easily found out using char -‘A’ + 1 expression. Rest is to just add each of the value to get the result. Hence our formula is
result  = result + S[i] * power(26, len-i-1) where i = 0 to len-1
It is fairly simple to code it.

int power(int i){

   if(i==0)
      return 1;
   if(i == 1) return 26;
   else{
        int temp =  power(i/2);
        if(i%2){
              return 26 * temp *temp;
        }
        else
              return temp * temp;
   }
}
void excel_column(char *s){

 int i ;
 int len  = strlen(s);
 int rank =0;
 for(i=0; i<len;i++){
        rank += power(len-i-1) * ((s[i]-'A')+1);
 }
 printf("%d", rank);
}

The complexity to convert excel column to an equivalent number code is O(N) where N is the size of the string.

Find words in maze

Find words in a maze

We learned basics of tries in last post. Let’s see if we could apply some of those properties in solving some real problems. Today’ problem at hand is to find all the words which are present in a maze of characters of size NxN. The condition is that characters of words should be adjacent to each other either horizontally or vertically.
For example, below maze contains cat, dog and word words in it.

What is the brute force solution? Simple, find all the words which can be formed using these characters in maze starting of length 1 to N*N. For each word check if the given dictionary contains the word, if yes, store that word in the result.
What is the search space here? There will be (n2!) words to be looked into the dictionary. Not a practical solution. Optimizing search in the dictionary using sorting and binary search will not be of much help. (Good point to mention at interview though).
So how can we reduce the search space? Let’s first take an example and see what is happening in the brute force approach.
If we look closely, we are checking string length N, even though we already know that N-1 character string leading to it is not a valid string. Can we avoid it? Yes, using tries. This is how we can do it.

Store all words in the given dictionary in a trie. If there is no prefix in trie with length = i; there cannot be the word with i+1 length having this prefix of length i. So just abort the lookup of words with this prefix. Else increase the string length by 1 and repeat the above step. Trie fits perfectly in this algorithm as we are dealing with prefixes. We need to keep track that what we have already visited and if there can be more words with the visited prefix. If we take the example of the above maze, we start from ‘a’, as we see that there is no word starting with ‘a’ in trie by looking at children array of the root, we can safely avoid calculating words starting with ‘a’ of any length from there.

Find words in a maze : Implemenetation

#include<stdio.h>
#include<stdlib.h>

#define N 4

int search_key(Node *current, char key){
   int index  =  GET_CHAR_INDEX(key);

   if(current->children[index] == NULL) return false;

   return true;
}

enum direction {
        NORTH =1,
        SOUTH,
        LEFT,
        RIGHT
};

void update_params(int row, int col, int *new_row, int *new_col, int dir){
   switch(dir){
      case NORTH:
           *new_row = --row;
           *new_col = col;
      break;
      case SOUTH:
           *new_row = ++row;
           *new_col = col;
      break;
      case LEFT:
           *new_col =  ++col;
           *new_row = row;
      break;
      case RIGHT:
           *new_col =  --col;
           *new_row = row;
      break;
     }
}


void find_words_wrapper(trie *t, char maze[][N]){

  int i,j,len, prefix_found = false;
  for(i=0; i<N; i++){
     for(j=0; j<N; j++){

    /*Consider all length words which can be formed stating with maze[i][j] char */

      for(len =1; len <N*N; len++){
        /* To check if we need to check for further length 
           1. if prefix_found = false, don't check, 
           no words possible for larger length 
           2. if prefix_found = true, continue looking*/

           prefix_found = false;

           /* If finally reached at the leaf of trie starting 
              with maze[i][j] and length = len */

              if(find_words(t->root, maze, len,i,j, &prefix_found)){
                 printf(" Word found at (%d %d)\n", i,j);
              }
              else if(prefix_found == false)
                 break;
       }
     }
   }
}

int valid_position(int row, int col){
        if(row<0 || row>N-1 || col <0 || col>N-1) return false;

        return true;
}

int find_words(Node *t, char maze[][N], int curr_len, 
               int curr_row, int curr_col, int *prefix){
       
       int new_row, new_col;
       int  dir,i;
       char key = maze[curr_row][curr_col];

       Node * current = t->children[GET_CHAR_INDEX(key)];

    /* Before finish the prefix we hit the null, prefix is not present */
       if(current == NULL) return false;

       /* If reach the prefix of len = curr_len but its not a word, 
        we can look forward with len = curr_len +1 */
       if(curr_len == 1 && current->value != LEAF_NODE){
                *prefix = true;
                return false;
       }
     /* If we reach at the leaf node, for this length, 
      we found a word with length = curr_len */
       if(curr_len == 1 && current->value == LEAF_NODE)
                return true;

       /* For every character look in all direction */
       for(dir = NORTH; dir<= RIGHT; dir++){

         /* if the key is present */
         if(search_key(t, key)){
         /* Move to next character based on direction of movement */
            update_params(curr_row, curr_col, &new_row, &new_col, dir);

            /*Validate that we are good in maze */
             if(valid_position(new_row, new_col)){

             /*Find word with len -1 in remaining trie */
              if(find_words(current, maze, curr_len-1, new_row, new_col, prefix)) {
                   return true;
               }
             }
          }
          else{
              return false;
          }
       }
}
void main(){

        trie t;
        initialize(&t);
        int i;

        char *dict []  = {"cat", "dog", "word"};

        char maze[N][N]  = { 'a' , 'c', 'a', 't',
                             'd' , 'w', 'o', 'r',
                             'o',  'g', 'd', 'd',
                             'p', 'p',  'p', 'p'
                           } ;
        for(i =0; i <3; i++){
                insert(&t, dict[i]);
        }

         find_words_wrapper(&t, maze);
}

Even though we have reduced the search space, we may end up looking at all the words i.e (n2!). There is a way to reduce it by using dynamic method approach, we look at that in the future.

Tries as data structure

Tries as data structure

Tries is a data structure which is usually neglected by programmers while designing solutions. Tries are very useful in cases where strings are involved with a good amount of duplication of their prefixes. What are tries? Trie is a data structure which stores information, referred to as key, in such a manner that the common information is stored only once. Usually keys are strings. No node in trie stores the whole key, but the position of the node gives us information that which key it is part of. All the descendant node in trie have the same prefix, hence trie is also know as prefix trees.Word trie is taken from retrieval word.

Another property of trie is that every node of trie has multiple children. In case of string (assuming lower case), there will be 26 children of each node. Take an example: We have the following strings: “House”, “Home”, “Tree” I need to store this information, Trie for the above words would look like:

Trie data structure example

Insertion in trie

Before insertion, we need to understand that how can we represent a node of a trie. Since intermediate nodes of a key do not store any information at them, we need to distinguish between the leaf node and the intermediate node. For that we can store a field called as the value inside each node, If the value is zero, it’s an intermediate node, if non-zero, it’s a leaf node.
In our case, we are assuming MAX_SIZE of 26.
Basic initialization

#define MAX_SIZE 26

#define GET_CHAR_INDEX(ch)\
        ((int) ch - (int)'a' )

#define LEAF_NODE  1
#define true 1
#define false 0

typedef struct trie_node_t {
        int value;
        struct trie_node_t * children[MAX_SIZE];
}Node;

typedef struct trie{
        int count ;
        Node *root;
}trie;

void initialize(trie *t){
        t->root = (Node *)malloc(sizeof(Node));
        t->count =0;
}

Now we can go and see insertion part.
Scan through the string character one by one. For each character, check if it has child nodes. The character acts as an index in children array. If the node at the char index has a child node, move to the child node and take the next character of the string. Repeat step 2 and 3 If the node at the char index doesn’t have a child node, create a child node and add it to trie. Move the character in the string and move down to a newly created child. Go to step 2.

void insert(trie *t, char key[]){

        int len = strlen(key);
        int i;

        if(t->root == NULL){
                printf("\n Trie is not initialized\n");
        }

        Node * current = t->root;
        for(i=0; i<len; i++){

             /* Get the index of char in children array */
             int index  =  GET_CHAR_INDEX(key[i]);

             /* If the children array does not contain the pointer
                at index pointed by char, allocate new node */

             if(current->children[index] == NULL){
                current->children[index] = (Node *)malloc(sizeof(Node));
             }
             /* Else traverse down the trie. */
             current = current->children[GET_CHAR_INDEX(key[i])];
        }

        /* To mark it as leaf */
        current->value = LEAF_NODE;
}

Search in trie
The best part of the trie is its search. It is done in O(M) where M is the length of the input string.
Start from the root. and take the first character of the string. If the array index pointed by the character is NULL, return false. Else move to the child node and next character. Repeat step 2 and 3 till the end to the input string. If we reach till the end of the string and the current node is a leaf node (identified using value), then return true.

int search(trie *t, char key[]){
        int len = strlen(key);
        int i;
        if(t->root == NULL){
                printf("\n Trie is not initialized\n");
        }

        Node * current = t->root;
        for(i=0; i<len; i++){
                int index  =  GET_CHAR_INDEX(key[i]);

                /* If characters are left in key and we have 
                reached at NULL, there is no key present */
                if(current->children[index] == NULL) return false;
                 
                /* Else traverse down the trie */
                current = current->children[index];
        }

        /* If we have reached the lead=f node, key is present */
        if(current && current->value == LEAF_NODE )
                return true;

        return false;
}

The only drawback with tries is that it takes a lot more space (K *  MAX_SIZE * N) as compared to the binary search tree. It is evident from the fact that every node in trie has to have a place for all the possible characters. In time complexity terms, insertion and search both are O(M) where M is length of string being entered. In this post we saw insertion and search operation in tries. We will use these operations in the future post and solve some real problems.

Remove particular combination of characters

Remove particular combination of characters from string.

Given a string, we need to remove a particular combination of characters, for example, if s = “aacbbdccaac” and if combination is “ac” then our output will be “abbdcca”. If s = “aacaaccd” and if combination is “ac”, then output should be “acd”. Following will be the execution  aacaaccd ——-> aacd ——>ad 
Note that this has to be done in linear time and without any extra space.

Here there are two subparts of the problem: One, we need to keep track we have already encountered the first character in the combination of characters needed to be removed.
Second we need to keep track of the position where the next character should be placed in the string if it is not to be eliminated. First problem can be easily solved by maintaining a state machine, where we have two states and one moves from one state to another based on the input. In current example, we have states like state “INITIAL” and “MOVED”, Whenever we encountered “a”, we move from INITIAL to MOVED. Then if we get “c” in “MOVED” state we are sure that we have encountered the whole pattern and they need to be removed. If we are in “MOVED” state and if we don’t get “c”, we move back to “INITIAL” state.

For the second part, we can simply follow the approach we have used in this post, that is to maintain two pointers, one to point to the character to be processed, and other to point position where current character to be placed if it is not be eliminated.
The problem can be extended with multiple characters in pattern, with change in state machine accordingly.Same state machine method can be used to count number of words in a given string. Whenever we encounter the separator, we move to OUT state and as soon as we see first character in OUT state we move to IN state till we again see separator.

#define INITIAL 1
#define MOVED 2
char * remove_pattern(char *s, char * pattern){
    int state = INITIAL;
    if(s == NULL) return NULL;
    if(pattern == NULL) return s;

    char * source = s;
    char * destination  = s;
    while(*source != ''){

        /*If character is not equal to the first character of the pattern,
          copy it as such */
          if(state == INITIAL && *source != *pattern){
               *destination = *source;
               destination++;
          }
          else if( *source == *pattern && state == INITIAL){
              /* Move state to MOVED */
              state = MOVED;
          }else if(state == MOVED && *source != *(pattern + 1)){
                /* If next character is not as per pattern, 
                   copy previous character first. */
                *destination =  *pattern;
                destination++;
                /* If next character is first character of the pattern,
                   move state to INITIAL */
                   if(*source != *pattern){
                       *destination  = *source;
                       destination++;
                       state =  INITIAL;
                   }
             }
         /* If we hit the pattern, start again and move state to INITIAL */
          else if(state == MOVED && *source == *(pattern + 1)){
                state = INITIAL;
          }
          /* After moving the characters, check if they 
            don't make pattern again */
          if((int)(destination-s) >= 2
              && *(destination -2) == *pattern
              && *(destination-1) == *(pattern +1)){
              destination -=2;
          }
          source++;
    }
    *destination = '';
    return s;
}

Test cases
1. When pattern is present
s= “aaacacacbbb” pattern = “ac”

2. When pattern is not pattern
s =”aaaabdcaaa” pattern  = “ac”
3. When movement leads to pattern again
s= “abacaccdc” pattern =”ac”

4. When string is NULL or pattern is NULL s= NULL pattern = NULL
5. When return string is empty s = “acacacac” pattern =”ac”

6. Just first character in pattern s= “aaaaaaaaa” pattern =”ac”

The complexity of the above code is O(N) and no extra space used.