Onsite Round
Position: SSE
Location: Hyderabad

Given a string, traverse right to left and increment any character value(i-th) if it is the same as previous character(i-1-th) in the string.
Once incremented, re-start the right to left traversal and repeat.
Repeat until there are no repeating adjacent characters.
(Traversing from right to left)
For e.g.

1. AA -> AB
2. AAA -> AAB ->ABB -> ABC
3. ZZZ -> ZZA -> ZAA -> ZAB
4. AAAA -> AAAB -> AABB -> AABC -> ABBC -> ABCC -> ABCD
5. AABB -> AABC -> ABBC -> ABCC -> ABCD
6. AAAMCCC -> AAAMCCD -> AAAMCDD -> AAAMCDE -> AABMCDE -> ABBMCDE -> ABCMCDE
7. AABBCC -> .... -> .... .. .... -> ABCDEF
8. AAAABB -> .... -> .... .. .... -> ABCDEF
9. AAAAAA -> .... -> .... .. .... -> ABCDEF

The brute force approach is to traverse the string from right to left (n-1 to 0).
When a duplicate is enountered, i.e. i-th char is the same as (i-1)-th, increment i-th char and restart traversal from right to left(n-1 to 0).
Repeat until there are no more adjacent repeating characters. This would be O(n2)
Interviewer started with explaining the brute force approach and asked to optimized it.

Please could anyone suggest an optimized approach for this.
Thanks