Tuesday, June 5, 2012

Repeating substring

Q: Given a string S find the smallest sub-string X such that S = (X)+, i.e. S is a repetition of one or more X's.

Soln approach: 
  • Iterate string from start to end keeping 2 pointers pointing to certain indexes in the string
    • The first one indicating endIndex of the sub-sequence X found till now
    • The second one indicating the index with which we must compare the character read in the next iteration
  • Update both the indexes in each iteration based on whether the character read matches the sub-sequence 
  • At the end X will be the sub-string from 0 to the first index mentioned in first point above
Java code:

No comments: