Problem Statement

Given two strings, s and goal, determine if goal is a rotation of s. A string goal is considered a rotation of s if we can take some leading number of characters from s and append them to the end of s to obtain goal.

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.

Examples

Example 1:

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

Explanation : After performing 2 shifts we can achieve the goal string from string s.
After first shift the string s is => bcdea
After second shift the string s is => cdeab.

Example 2:

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

Explanation : Any number of shift operations cannot convert string s to string goal.

Example 3
Input : s = "abcde" , goal = "abcde"

Output :
true

Constraints

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

Approach

1️⃣ Iteration

Intuition

To address this problem, a solution could be to generate all possible rotations of the string and verify if any of these rotations match the target `goal` string. The approach involves systematically creating each rotation and comparing it against the `goal`, which ensures that if a matching rotation exists, it will be identified.

Approach

1. First generate all possible rotations of the string by rearranging its character using the substring method.
2. For each rotation created, check if it is the same as the goal string.
3. If any rotation matches the goal, return true; otherwise, after testing all rotations, return false.

Dry Run

Initialization

index    0     1     2     3     4
      -------------------------------
str   |  a  |  b  |  c  |  d  |  e  |
      -------------------------------

      -------------------------------
goal  |  c  |  d  |  e  |  a  |  b  |
      -------------------------------

First Pass

index    0     1     2     3     4
      -------------------------------
str   |  a  |  b  |  c  |  d  |  e  |
      -------------------------------
         ^
         |
         i = 0
 
 rotated str => substr(i, n) and substr(0, i)
        -------------------------------        
  str1  |  a  |  b  |  c  |  d  |  e  |  +  str2 (empty string)
        -------------------------------

      -------------------------------
goal  |  c  |  d  |  e  |  a  |  b  |
      -------------------------------
 
rotated str != goal
Increment 'i'

Second Pass

index    0     1     2     3     4
      -------------------------------
str   |  a  |  b  |  c  |  d  |  e  |
      -------------------------------
               ^
               |
               i = 1
 
 rotated str => substr(i, n) and substr(0, i)
        -------------------------          -------
  str1  |  b  |  c  |  d  |  e  |  +  str2 |  a  |
        -------------------------          -------
        
                -------------------------------
rotated str ->  |  b  |  c  |  d  |  e  |  a  |
                -------------------------------

      -------------------------------
goal  |  c  |  d  |  e  |  a  |  b  |
      -------------------------------
 
rotated str != goal
Increment 'i'

Third Pass

index    0     1     2     3     4
      -------------------------------
str   |  a  |  b  |  c  |  d  |  e  |
      -------------------------------
                     ^
                     |
                     i = 2
 
 rotated str => substr(i, n) and substr(0, i)
        -------------------          ---------------
  str1  |  c  |  d  |  e  |  +  str2 |  a  |   b   |
        -------------------          ---------------
        
                -------------------------------
rotated str ->  |  c  |  d  |  e  |  a  |  b  |
                -------------------------------

      -------------------------------
goal  |  c  |  d  |  e  |  a  |  b  |
      -------------------------------
 
rotated str == goal
Returns TRUE

Code

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool rotateString(string& s, string& goal) {
    // Strings must be same length to be rotations of each other
        if (s.length() != goal.length()) {
            return false;  
        }
        // Try all possible rotations of s
        for (int i = 0; i < s.length(); i++) {
            string rotated = s.substr(i) + s.substr(0, i);  
            if (rotated == goal) {
                return true;  
            }
        }
        return false;  
    }
};

int main() {
    Solution sol;
    string s = "abcde";
    string goal = "cdeab";
    cout << (sol.rotateString(s, goal) ? "true" : "false") << endl;  
    s = "abcde";
    goal = "abced";
    cout << (sol.rotateString(s, goal) ? "true" : "false") << endl;  
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N^2) Generate N rotations and each comparison takes O(N) time.
• Space Complexity:O(N) for the space needed to store each rotated string.

2️⃣ Optimal Approach

Intuition:

The optimal approach solves the problem by concatenating s with itself to form s + s. This way, all possible rotations of s are included as substrings in s + s, so we just need to check if goal is a substring of s + s.

Approach:

1. Create a new string by concatenating s with itself, resulting in s + s.
2. Check if goal is a substring of s + s.
3. If goal is found within s + s, return true; otherwise, return false.

Dry Run:

index     0     1     2     3     4
       -------------------------------
str    |  a  |  b  |  c  |  d  |  e  |
       -------------------------------
       -------------------------------
goal   |  c  |  d  |  e  |  a  |  b  |
       -------------------------------

index     0     1     2     3     4
       -------------------------------
str    |  a  |  b  |  c  |  d  |  e  |
       -------------------------------
       -------------------------------
goal   |  c  |  d  |  e  |  a  |  b  |
       -------------------------------

Create a new string doubledStr = str + str
           -------------------------------------------------------------
doubledStr |  a  |  b  |  c  |  d  |  e  |  a  |  b  |  c  |  d  |  e  |
           -------------------------------------------------------------
                          ^                       ^
                          |-----------------------|

   Search for goal in new string doubledStr
   'goal' was found at index 2
   Return TRUE

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
// Strings must be of the same length to be rotations of each other
    bool rotateString(string& s, string& goal) {
        if (s.length() != goal.length()) {
            return false;  
        }
        string doubledS = s + s;  // Concatenate s with itself
        return doubledS.find(goal) != string::npos;  // Check if goal is a substring of s + s
    }
};

int main() {
    Solution sol;
    string s = "abcde";
    string goal = "cdeab";
    cout << (sol.rotateString(s, goal) ? "true" : "false") << endl;  
    s = "abcde";
    goal = "abced";
    cout << (sol.rotateString(s, goal) ? "true" : "false") << endl; 
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N), because checking for a substring in s + s is linear in time.
• Space Complexity:O(N) for the space needed to store the concatenated string s + s.