Monday, December 29, 2014

Find all the repeating sub-string sequence

Find all the repeating sub-string sequence of specified length in a large string sequence. The sequences returned i.e. the output must be sorted alphabetically. 

For e.g. 

Input String: "ABCACBABC" 
repeated sub-string length: 3 

Output: ABC 

Input String: "ABCABCA" 
repeated sub-string length: 2 

Output: AB, BC, CA

Click here for the original problem.
Ha, very interesting problem. I was wondering why all the add() methods returns boolean type. Now I  know, since Set doesn't allow duplicate values,  if add() returns false, it means the set fails to add the value, which probably imply there already exists the value. And in this problem, we are utilizing this feature.


import java.util.*;
public class RepeatingSubstring {
 public ArrayList repeatSubstring (String s, int length) {
  if (s == null)
   throw new NullPointerException("Null array");
  ArrayList rst = new ArrayList ();
  if (s.length() == 0)
   return rst;
  HashSet nonRepeating = new HashSet ();
  TreeSet repeating = new TreeSet ();
  for (int i = 0; i + length <= s.length(); i++) {
   if (!nonRepeating.add(s.substring(i, i + length)))
    repeating.add(s.substring(i, i + length));
  }
  rst = new ArrayList (repeating);
  return rst;
 }

}

No comments:

Post a Comment