# What would be the optimum approach for this string problem?

Today, in an interview, I was asked this programming question:

Given a string, w, following two operations are performed alternatively per day.

1. Remove last m characters from w and prepend them to w. m is less than length of w.
2. Remove last n characters from w and prepend them to w. n is less than length of w.

Find how many days would it take to get back w if we start to perform the above operations.

For example, if w is abcde and m is 2 and n is 3, then

original w: abcde after m op, w: deabc after n op, w: abcde

stop since new string abcde is same as the original string w = abcde

My approach was the brute force one where I had a loop and was performing both of the above operation and was continuously checking if the new w is same as the original w. However, this approach is definitely not scalable.

• You have to find the smallest $k$ such that $km+kn$ or $km+(k-1)n$ is a multiple of the length $N$ of $w$. Those are Diophantine equations you can solve. Problem is, some manipulations of $w$ could be equal to $w$, (for example, if $w=aaaaa$, one day gets you back to the original string !) so your "Brute force" approach, if correctly implemented, is, IMO, as good as a tricky math exploration... – Nicolas FRANCOIS Jul 8 '19 at 4:27
• For the test case, w = abcde, m =2 and n = 3, k = 1 satisfies (km +kn) to be multiple of length N. However, the correct answer is 2 not 1. – user3243499 Jul 8 '19 at 4:40
• It should be $2k$ if $m$ and $n$ characters are removed the same amount of times and $2k-1$ if $m$ is removed one more time. – Varun Vejalla Jul 8 '19 at 5:05
• Are all characters of the string distinct? – Varun Vejalla Jul 8 '19 at 5:05
• @automaticallyGenerated: Are all characters of the string distinct? Not necessarily. – user3243499 Jul 8 '19 at 5:14

Assume the string consists of the integers $$1$$ through $$N$$ in sequence, so $$N$$ is the length of the string. Apply the operations 1 and 2 to the string. Interpret the resulting string of integers as a permutation of the original string. Write this permutation as a product of disjoint cycles. The period of the permutation is the least common multiple of the lengths of the cycles.