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:
Post a Comment