Rotate String Problem

Problem

Given two string s1 and s2 how will you check if s1 is a rotated version of s2 ?

OR

Assume you have a method isSubstring() which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring.

OR

Given two strings s and goal, return true if and only if s can become goal after some number of shifts on s.

A shift on s consists of moving the leftmost character of s to the rightmost position.

• For example, if s = "kodeknight", then it will be "odeknightk" after one shift.

Examples

Example 1:

1
2

Input: s = "abcde", goal = "cdeab"
Output: true

Example 2:

1
2

Input: s = "abcde", goal = "abced"
Output: false

Solutions

Method 1 - Club One of the String and Rely Upon Substring Method

To determine if string s can become string goal after some number of shifts, the key observation is:

• A shift operation can be visualised as a rotation of the string.
• If we concatenate s with itself (s + s), all possible rotations of s are contained within this concatenated string.

Thus, if goal is a rotation of s, it will be a substring of s + s.

Steps to solve:

1. Check if s and goal have the same length. If not, return false.
2. Check if goal is a substring of s + s.

Here is the solution :

• First make sure s1 and s2 are of the same length.
• Check to see if s2 is a substring of s1 concatenated with s1.

1
2
3
4
5
6
7

boolean checkRotation(string s1, string s2)
 if( len(s1) != len(s2))
 return false
 if( substring(s2,concat(s1,s1))
 return true
 return false
end

Code

1
2
3
4
5
6
7
8
9

public class Solution {
    public boolean rotateString(String s, String goal) {
        if (s.length() != goal.length()) {
            return false;
        }
        String doubled = s + s;
        return doubled.contains(goal);
    }
}

1
2
3
4

boolean isRotation(String s1,String s2) {
 return (s1!=null && s2!=null &&
 s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}

1
2
3
4
5
6

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False
        doubled: str = s + s
        return goal in doubled

Complexity

• ⏰ Time complexity: O(n^2), where n is the length of string s.
• 🧺 Space complexity: O(n)

Method 2 - Rolling Hash

We can use Rabin Karp algorithm using rolling hash to implement substring method.

Complexity

• ⏰ Time complexity: O(n), where n is the length of string s.
• 🧺 Space complexity: O(n)

Method 3 - Knuth Morris Pratt

We can use KMP algorithm to implement substring method.

Complexity

• ⏰ Time complexity: O(n), where n is the length of string s.
• 🧺 Space complexity: O(n)