## Remove duplicate characters

Given a string, remove consecutive duplicate characters from the string. For example:

```Input:
S = "aabccacc"
Output:
"ba"

Input:
S = "accacc"
Output:
""
```

Solution for this problem is in the idea that we need two pointers, one to read a character and another to write a character.
In this case, let’s say we take two pointers, i and j, where i points to the index where next character will be written, whereas j will is the position of current character.

As String in most languages is an immutable object and we are planning to modify it, it is better idea to convert string to a character array. For each character at index j, we will copy it at index i. Check if the chars[i-1] and chars[i] are equal? If yes, we found consecutive duplicate characters.
If found duplicate characters, we will move i to i-2 to remove both instances of the character. If not, nothing changes.

## Removed consecutive duplicates from string implementation

```package AlgorithmsAndMe;

public class RemovedDuplicates {

public String removeDuplicates(String s){

char [] res =  s.toCharArray();
int i = 0;
int [] count = new int[res.length];
for(int j=0; j<res.length; j++, i++){
res[i] = res[j];

if(i > 0 && res[i] == res[i-1]){
i -=2;
}
}

return String.valueOf(res).substring(0, i);

}
}
```

Sometimes the same question is asked with k as parameters: given a string, remove all consecutive K duplicate characters.
For example:

```Input:
S =  deeedbbcccbdaa, K = 3.
Output:
"aa"
```

The idea is the same, keep two pointers i and j, one for writing and another for reading. We will copy the character onto the index i. If the new character is the same as the previous character, we increment the count. If not, we reset the count. If count is equal to k, we remove all the instance of the character by moving i by k to the left.

```package AlgorithmsAndMe;

public class RemovedDuplicates {

public String removeDuplicates(String s, int k){

char [] res =  s.toCharArray();
int i = 0;
int [] count = new int[res.length];
for(int j=0; j<res.length; j++, i++){
res[i] = res[j];

count[i] = i>0 && res[i-1] == res[j] ? count[i-1] + 1 : 1;

if(count[i] == k){
i -=k;
}
}

return String.valueOf(res).substring(0, i);

}
}
```

The time complexity of both the implementations is O(n).

## 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

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.

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.

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.

## Group Anagrams

Many a times we need to sort some things which are not integers, foremost being strings. How do we go about using quicksort? I did not know that the C library has a function for it. This function is very powerful and easily sort anything given the compare function. So in today’s post, we will be using that function and learn how it can be used to solve our problem statement.

Given a list of words, group all words together which are anagrams. For example, if the input is like :

`cat tac act dog god gdo`

First of all, we want to understand how to strings can be identified as anagrams. There are more efficient ways to do it, but the most simple one is sort two string based on characters and if two resultant strings match, two strings are anagrams.
Now the problem boils down to sorting each individual string and then sort the entire array of strings. The anagram strings will automatically grouped together.
If we look closely, we have another problem, that is when we sort the original strings individually, original strings are lost. So, idea is to have a duplicate array of strings and then sorting operation. Also to after sorting the duplicate array, we will lose the original index of string once we sort the entire array. Hence we need to store that information too. Let’s figure what we need to store and how? We have array of strings, let’s say there can be a maximum 100 such strings. So we create an array of character pointers to store these strings. Also, we need a duplicate array where we will sort strings and also we need to store the position of the string in original array so, the duplicate array would look like:
Next step is to sort individual string in the duplicate array, where we will use the library function qsort().
This function is very easy to use, there are four parameters you have to pass:
1. The buffer or the array you want to have sorting performed on.
2. The size of the buffer
3. Size of an individual element of the buffer.
4. And last and most important is the compare function, which has to be written in code and passed as function pointer to this function. For further details of qsort() function usage follow : qsort
Once all the strings are individually sorted, sort the entire array of strings using the same qsort(), only difference will be the compare function which will now run on an entire string instead of character. We are almost done! Now we have all anagrams placed next to each other, however, we need to print original words. That’s where the index we stored in duplicate array will help and we will print words from original array using the order given in the duplicate array.

```class Solution {
public List<List<String>> groupAnagrams(String[] strs) {

Map<String, List<String>> map = new HashMap<>();

for(int i=0; i < strs.length; i++){
char [] temp = strs[i].toCharArray();
Arrays.sort(temp);

String keyString  = String.valueOf(temp);

if(!map.containsKey(keyString)){
map.put(keyString, new ArrayList<>());
}
map.get(keyString).add(strs[i]);
}

return new ArrayList<List<String>>(map.values());
}
}
```

This code will perform sorting on M strings, each of size N characters, so the complexity of the algorithm to print all anagrams together will be O(MlogM + MNlogN) MNlogN because NlogN for sorting each string of size N and there are M strings, MlogM to sort M strings in the array.

# 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.

## Unique rows in boolean matrix

Given a matrix of 0 and 1, print all unique rows in boolean matrix. For example, if the matrix is show below:
0 1 0 0 1
1 0 1 1 1
0 1 0 0 1
1 0 1 0 0
Output should be
0 1 0 0 1
1 0 1 1 1
1 0 1 0 0

The first brute force solution which has a complexity of O(n2 m) where is n is the number of rows and m is the number of columns is as follows:
For each row in the boolean matrix, check all the rows if it matches with any one of them. If yes, skip printing, else print the row.
Another way which is better than the above approach is to convert each row in equivalent decimal and then check for duplicates. Again it has a complexity of O(n * m) where n is the number of rows and m as the number of columns.

Can we do better than this? There is a standard technique to check if a particular pattern is already seen or not. That’s using tries. Each pattern is added to trie, when we try to add a duplicate pattern, we will end up at the leaf node which is already marked as leaf due to an earlier pattern.
With given info, we can say that we will insert each row pattern in the trie. We will modify the insert function of trie to return us whether the row is added newly or it was already present in the trie. As explained above it can be ascertained by the fact that if the last node is marked as leaf node already, then it is duplicate row as we must have traveled the same nodes above. If the last node is not a leaf node already, then there is at least one digit which is different and hence row becomes unique. Mark last node of this pattern as a leaf node, so that same patterns will be detected as duplicates.

Add a row in the trie.
If the last node while entering the pattern is the leaf node, return false. It’s not a unique row.
If the last node is not a leaf node, mark it as a leaf node and return true.
If insert operation returns true, print the row.
Else, skip printing row.

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

#define MAX_SIZE 2

#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;
}

int insert_1(trie *t, int key[], int col){

int i;

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

Node * current = t->root;
for(i=0; i<col; i++){
int index  =  key[i];
if(current->children[index] == NULL){
current->children[index] = (Node *)malloc(sizeof(Node));
}
current = current->children[key[i]];
}

/* To mark it as leaf */
if(current->value != LEAF_NODE){
current->value = LEAF_NODE;
return true;
}
else{
return false;
}
}

void print_unique_rows(int a[5][5], int col, int row){

int i,j;
int key[col];

trie t;
initialize(&t);
for(i=0; i<row; i++){
for(j=0; j<col; j++){
key[j] = a[i][j];
}
if(insert_1(&t, key, col)){
for(j=0;j<col; j++){
printf("%d", key[j]);
}
printf("\n");
}
}
}
//Driver program
int main(){

int a[4][5] = {{0, 1, 0, 0, 1},
{1, 0, 1, 1, 0},
{0, 1, 0, 0, 1},
{1, 0, 1, 0, 0}
};

print_unique_rows(a, 5, 4 );

return 0;
}
```

The complexity of trie based solution is O(n * m).

# 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 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 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:

## 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.

# Word break problem

This problem is commonly asked in the Google and Amazon interview. We all know that if you typed string in Google search box does not make sense, Google breaks that into meaningful words and asks us back if we meant those words instead of a single word. This post discusses how can we find if the given string can be broken into meaningful dictionary words. For example, if I typed algorithmsandme and given dictionary is [“algorithms”, “and”, “me”], this string is breakable in meaningful words. but if the string is algorithmsorme this is not breakable into meaningful words. You can find this problem for practice at leetcode.

## Word break problem : thoughts

We start with the first character of the string, check if the character itself is a word in the dictionary? If yes, then our problem reduces to the smaller problem, that is to check if substring from index 1 to s.length is breakable or not.
If not, then we check two characters and then three characters and so on till we can check the whole string. As with every character inclusion, the problem reduces in size but remains the same, so ideal case for recursive implementation.

```package AlgorithmsAndMe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {

public boolean wordBreak(String s, List<String> wordDict) {
return wordBreakUtil(s, wordDict, 0, table);
}

private boolean wordBreakUtil(String s,
List<String> wordDict,
int index) {

if (index == s.length()) return true;

boolean isBreakable = false;
for(int i=index; i<s.length(); i++) {
isBreakable = isBreakable
|| wordDict.contains(s.substring(index, i+1))
&& wordBreakUtil(s, wordDict, i + 1);
}

return isBreakable;
}
}

```

If you notice we are solving the same problems again and again in recursive function `wordBreakUtil`, how can we save that repeated calculations? Best way to save the already solve problems in a cache, that way we can refer to the cache if the problem is already solved or not. If yes, do not solve it again and use the cached value. This approach is called a Top Down approach and uses memoization to avoid repeated subproblems.

```package AlgorithmsAndMe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {

public boolean wordBreak(String s, List<String> wordDict) {
int [] table =  new int[s.length()];
for(int i=0; i<s.length(); i++){
table[i] = -1;
}
return wordBreakUtilTopDown(s, wordDict, 0, table);
}

private boolean wordBreakUtilTopDown(String s,
List<String> wordDict,
int index,
int[] table) {

if (index == s.length()) return true;

if(table[index] < 0) {
boolean isBreakable = false;
for (int i = index; i < s.length(); i++) {
isBreakable = isBreakable
|| wordDict.contains(s.substring(index, i + 1))
&& wordBreakUtilTopDown(s, wordDict, i + 1);
}
table[index] = isBreakable ? 1 : 0;
}
return table[index] == 1 ? true : false;
}
}

```

If you run the first solution, it will exceed the time limit on leetcode, however, the second implementation should be accepted with 4ms as the time to run. Now you can appreciate the efficiency by memoization.

### Word break problem using dynamic programming

In the last two implementations, two things are evident: first, the optimal solution of a subproblem leads to the optimal solution of the original problem. Second, there are overlapping subproblems. These are two must have conditions for applying dynamic programming. We already saw the memoization and top-down approach of DP to avoid repeated solving of subproblems. How can we do it bottom up?

What if store an information if the string till index i is breakable? What will be the base case? The string before index 0 is alway breakable as empty string. So table[0] can be always true. To check if string till index i is breakable or not, we check from index 0 to index i-1 if there is any index j till which string is breakable. If yes, then we just check if substring from index j to i, that will make `table[i]` as true.

```package AlgorithmsAndMe;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {

public boolean wordBreak(String s, List<String> wordDict) {
return wordBreakBottomUp(s, wordDict, 0, table);
}

private boolean wordBreakUtilBottomUp(String s, List<String> wordDict){

if(s == null || s.length() == 0) return false;

boolean[] table  = new boolean[s.length()+1];

table[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = i - 1; j >= 0; j--) {
if (table[j] && wordDict.contains(s.substring(j, i))) {
table[i] = true;
}
}
}
}
return table[s.length()];
}
}
```

The time complexity of the above implementation of the word break problem is `O(n2)`

If you want to store all the strings which can be generated by breaking a particular word, below is the code.

```package AlgorithmsAndMe;

import java.util.*;

public class WordBreak2 {

public List<String> wordBreak(String s, List<String> wordDict) {
Map<String, List<String>> map = new HashMap<>();
return wordBreakUtil2(s, wordDict, map);
}

private List<String> wordBreakUtil2(String s,
List<String> wordDict,
Map<String, List<String>> map) {

if(map.containsKey(s)){
return map.get(s);
}

List<String> result = new ArrayList<String>();
if (wordDict.contains(s)){
result.add(s);
}

for(int i=1; i<=s.length(); i++) {
String prefix = s.substring(0, i);
if(wordDict.contains(prefix)){
List<String> returnStringsList = wordBreakUtil2(s.substring(i), wordDict, map);

for(String returnString :returnStringsList ){
result.add(prefix + " " + returnString);
}
}
}
map.put(s,result);

return result;
}
}

```

Please share if there is something is wrong or missing. If you are preparing for an interview and need any help with preparation, please reach out to us or book a free session.

# 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.