• Posts

Problem 796 Rotate String

Problem Statement

Link - Problem 796

Question

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 = "abcde", then it will be "bcdea" after one shift.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= s.length, goal.length <= 100
• s and goal consist of lowercase English letters.

Solution

class Solution {
public:
    bool rotateString(string s, string goal) {
        if(s.size()!=goal.size())
            return false;

        string test = s+s;
        int t = test.size(), g = goal.size();
        int j;
        for(int i=0; i<t-g; i++){
            j = 0;
            while(j<g && test[i+j] == goal[j]){
                j++;
            }
            if(j==g)
                return true;
        }

        return false;
    }
};

Complexity Analysis

| Algorithm                             | Time Complexity | Space Complexity |
| ------------------------------------- | --------------- | ---------------- |
| KMP variant with string concatenation | O(nm)           | O(n)             |

Explanation

Intial Thoughts

To solve this problem, consider the concept of a circular buffer where the string s is treated as a ring. The goal is to find if the string goal can be obtained by rotating this ring. Initially, think about the conditions under which s can become goal after some shifts. Consider the lengths of the strings and how shifts affect the position of characters. Think about how to efficiently compare all possible rotations of s with goal.

Intuitive Analysis

Intuitively, solving this problem involves understanding that a shift operation is essentially a circular rotation of the string s. The key insight is that if s can become goal after some shifts, then goal must be a substring of s repeated twice (s+s), because no matter how many times you shift s, you’re essentially looking at different parts of this doubled string. Thus, the solution involves checking if goal is a substring of s+s, which covers all possible rotations of s. This approach allows for an efficient solution by avoiding the need to actually perform the rotations and compare each time.

1. Intuition

• The problem can be approached by considering all possible shifts of the string s and checking if any of them match the goal string
• A key insight is that if s can become goal after some shifts, then goal must be a substring of s concatenated with itself
• This is because a shift operation is equivalent to moving the leftmost character to the rightmost position, which can be simulated by concatenating s with itself
• The solution works by checking all substrings of s+s that have the same length as goal to see if any of them match goal
• This approach ensures that all possible shifts of s are considered, and it does so in a way that is efficient and easy to implement
• The time complexity of this approach is O(n), where n is the length of s, because we are iterating over all substrings of s+s that have the same length as goal
• The space complexity is also O(n) because we need to store the concatenated string s+s

2. Implementation

• The solution starts by checking if the lengths of s and goal are equal, and if not, it immediately returns false because s cannot become goal after any number of shifts
• It then creates a new string test by concatenating s with itself, which allows us to simulate all possible shifts of s
• The solution then iterates over all substrings of test that have the same length as goal, and for each one, it checks if it matches goal by comparing characters one by one using a while loop
• If a match is found, the solution immediately returns true, indicating that s can become goal after some shifts
• If no match is found after checking all substrings, the solution returns false, indicating that s cannot become goal after any number of shifts
• The use of t = test.size() and g = goal.size() simplifies the code and makes it more readable by avoiding repeated calculations of the lengths of test and goal
• The variable j is used to keep track of the current position in the substring being compared to goal, and it is incremented as long as the characters match

Complexity Analysis

Time Complexity:

• The algorithm iterates over the concatenated string test with two nested loops, where the outer loop runs t-g times and the inner loop runs g times in the worst case, resulting in a time complexity of O((t-g)g). Since t = 2n and g = n, this simplifies to O(nn) = O(n^2) but is often reported as O(nm) where n and m are the lengths of s and goal respectively.
• The dominant operation is the while loop comparison test[i+j] == goal[j], which occurs for each character in the strings up to g times for each of the t-g starting positions.
• Justification of Big O classification lies in the fact that the number of operations grows quadratically with the size of the input strings, hence the O(n^2) or O(nm) classification.

Space Complexity:

• The algorithm creates a new string test which is the concatenation of s with itself, resulting in a space complexity that is directly proportional to the size of s.
• The impact of the data structure (in this case, the string test) is that it requires additional memory that scales linearly with the size of the input string s.
• Justification of the space complexity as O(n) arises from the fact that the memory usage is directly proportional to the size of the input string s, where n is the length of s.

Footnote

This question is rated as Easy difficulty.