CODEWITHSUNDEEP
stringalgorithm
John WK
John WK

Reputation: 121

Check if string contains consecutive repeated substring

I got an interview problem which asks to determine whether or not a given string contains substring repeated right after it. For example:

ATAYTAYUV contains TAY after TAY AABCD contains A after A ABCAB contains two AB, but they are not consecutive, so the answer is negative

My idea was to look at the first letter, find its second occurrence then check letter by letter if the letters after the first occurrence match the letters after the second occurrence. If they all do, the answer is positive. If not, once I get a mismatch, I can repeat the process but starting with the last letter I checked, since I would not be able to get a repeated sequence up to that point.

I am not sure if the approach is correct or if it is the mos efficient.

Upvotes: 2

Views: 63

Answers (1)

user1196549
user1196549

Reputation:

Assume that you are looking for a repeating pattern of length 3. If you write the string shifted right by three positions in front of itself (and trimmed), you can detect runs of 3 identical characters.

ATAYTAYUV 
   ATAYTA

Repeat this for all lengths up to N/2.

Upvotes: 1

Related Questions