Given a string s and an array of smaller strings T, design a method to search s for each small string in T.

First, create a suffix tree for s. For example, if your word were bibs, you would create the following tree:
                                                             I               S
                                            B
                                     I                               B
                                                    S
                             B                                              S
                     S
Then, all you need to do is search for each string in T in the suffix tree. Note that if “B” were aword, you would come up with two locations.

1        public class SuffixTree {
2                SuffixTreeNode root = new SuffixTreeNode();
3                public SuffixTree(String s) {
4                         for (int i = 0; i < s.length(); i++) {
5                               String suffix = s.substring(i);
6                               root.insertString(suffix, i);
7                         }
8                }
9           
10               public ArrayList<Integer> getIndexes(String s) {
11                        return root.getIndexes(s);
12               }
13       }
14   
15       public class SuffixTreeNode {
16               HashMap<Character, SuffixTreeNode> children = new
17                                                                 HashMap<Character, SuffixTreeNode>();
18               char value;
19               ArrayList<Integer> indexes = new ArrayList<Integer>();
20            public SuffixTreeNode() { }
21        
22            public void insertString(String s, int index) {
23                   indexes.add(index);
24                   if (s != null && s.length() > 0) {
25                           value = s.charAt(0);
26                           SuffixTreeNode child = null;
27                           if (children.containsKey(value)) {
28                                   child = children.get(value);
29                           } else {
30                                   child = new SuffixTreeNode();
31                                   children.put(value, child);
32                           }
33                           String remainder = s.substring(1);
34                           child.insertString(remainder, index);
35                   }
36            }
37        
38            public ArrayList<Integer> getIndexes(String s) {
39                   if (s == null || s.length() == 0) {
40                           return indexes;
41                   } else {
42                           char first = s.charAt(0);
43                           if (children.containsKey(first)) {
44                                   String remainder = s.substring(1);
45                                   return children.get(first).getIndexes(remainder);
46                           }
47                   }
48                   return null;
49            }
50     }
51   
52     public class Question {
53            public static void main(String[] args) {
54                   String testString = “mississippi”;
55             String[] stringList = {“is”, “sip”, “hi”, “sis”};
56             SuffixTree tree = new SuffixTree(testString);
57                   for (String s : stringList) {
58                  ArrayList<Integer> list = tree.getIndexes(s);
59                  if (list != null) {
60                             System.out.println(s + “: “ + list.toString());
61                  }
62                   }
63            }
64     }

Design a method to find the frequency of occurrences of any given word in a book.

Solution: Single Query
In this case, we simply go through the book, word by word, and count the number of times that a word appears. This will take O(n) time. We know we can’t do better than that, as we must look at every word in the book.

Solution: Repetitive Queries
In this case, we create a hash table which maps from a word to a frequency. Our code is then
like this:
1        Hashtable<String, Integer> setupDictionary(String[] book) {
2                Hashtable<String, Integer> table =
3                        new Hashtable<String, Integer>();
4                for (String word : book) {
5                        word = word.toLowerCase();
6                        if (word.trim() != “”) {
7                                if (!table.containsKey(word)) table.put(word, 0);
8                                table.put(word, table.get(word) + 1);
9                        }
10               }
11               return table;
12       }
13   
14       int getFrequency(Hashtable<String, Integer> table, String word) {
15               if (table == null || word == null) return -1;
16               word = word.toLowerCase();
17               if (table.containsKey(word)) {
18                       return table.get(word);
19               }
20               return 0;
21       }

Given a sorted array of strings which is interspersed with empty strings, write a meth- od to find the location of a given string.

Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4
Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1
                                                                                                                       
Use ordinary binary search, but when you hit an empty string, advance to the next nonempty string; if there is no next non-empty string, search the left half.

1      public int search(String[] strings, String str, int first, int last) {
2              while (first <= last) {
3                       // Ensure there is something at the end
4                       while (first <= last && strings[last] == “”) {
5                               --last;
6                       }
7                       if (last < first) {
8                               return -1; // this block was empty, so fail
9                       }
10                      int mid = (last + first) >> 1;
11                      while (strings[mid] == “”) {
12                              ++mid; // will always find one
13                      }
14                      int r = strings[mid].compareTo(str);
15                      if (r == 0) return mid;
16                      if (r < 0) {
17                              first = mid + 1;
18                      } else {
19                              last = mid - 1;
20                      }
21             }
22             return -1;
23     }
24        
25     public int search(String[] strings, String str) {
26             if (strings == null || str == null) return -1;
27             if (str == “”) {
28                      for (int i = 0; i < strings.length; i++) {
29                              if (strings[i] == “”) return i;
30                      }
31                      return -1;
32             }
33             return search(strings, str, 0, strings.length - 1);
34     }

Write a method to sort an array of strings so that all the anagrams are next to each other.

The basic idea is to implement a normal sorting algorithm where you override the compareTo method to compare the “signature” of each string. In this case, the signature is the alphabetically sorted string.

1      public class AnagramComparator implements Comparator<String> {
2               public String sortChars(String s) {
3                       char[] content = s.toCharArray();
4                       Arrays.sort(content);
5                       return new String(content);
6               }
7         
8            public int compare(String s1, String s2) {
9                    return sortChars(s1).compareTo(sortChars(s2));
10           }
11     }
Now, just sort the arrays, using this compareTo method instead of the usual one.
12     Arrays.sort(array, new AnagramComparator());

Length of unique subString in the given string

package arrays;

public class UniqueSubString {

public static void main(String[] args){

String s = "geeksforgeeks";
char[] str = s.toCharArray();
   int[] visited = new int[256];
   int max_length=1;
   int prev;

    //System.out.println(visited.length);
   for(int i=0;i<visited.length;i++)
    visited[i]=-1;
 
   visited[str[0]] = 0;
   int cur_length=1;

   for(int i=1;i<str.length;i++) {
    prev = visited[str[i]];
   if(prev == -1 || i-cur_length > prev){
    cur_length++;
   
   }
   
   else {
    if(max_length < cur_length)
    max_length = cur_length;
    cur_length = i - prev;
   
   }
   visited[str[i]] = i;
 
   }
 
   if(cur_length > max_length)
    max_length = cur_length;
   System.out.println(max_length);

}
}

The input : ABDEFGABEF
The length 6

Time Complexity: O(n + d) where n is length of the input string and d is number of characters in input string alphabet. For example, if string consists of lowercase English characters then value of d is 26.
Auxiliary Space: O(d)

Printing all combinations of given array of Strings

public static void comb(String[] a){
    int n=a.length;
    for(int i=1;i<Math.pow(2, n);i++){
      int pos=0;
      int j=i;
      while(j!=0){
        if((j & 1)==1){
          System.out.print(a[pos]);
        }
        pos++;  
        j=j>>1;  
     }
     System.out.println("");
     }
    }

Reversing the words in a Sentence

public class Rev_sentence {
 
  public static void main(String[] args) {
  String input = new String("HI ram");
  // op : mar IH => ram HI
  String reverse = new StringBuffer(input).reverse().toString();
  System.out.println(reverse);
 
  String[] str = input.split(" ");
 
  StringBuffer sb=new StringBuffer();
  for(int i=str.length-1;i>=0;i--){
    sb.append(str[i]);
    sb.append(" ");
  }
  System.out.println(sb);
 
  }

}