796. Rotate String

EasyStringString Matching

Problem Description

The problem presents a scenario where we have two strings, s and goal, and we are tasked with determining whether s can be transformed into goal through a series of shifts. A shift operation is defined as taking the first character from s and moving it to the end of the string. The task is to perform as many shifts as needed to check if s can match goal. We need to return true if it's possible and false otherwise.

Intuition

The intuition behind the solution is founded on the idea of concatenation and sub-string checking. By appending string s to itself, we create a new string that contains all possible shifts of s. This is because any shift of a string of length n is a sub-string starting from some index i to index i + n in the double-length string. If goal is a sub-string of this doubled string, then it must be possible to shift the original s to match goal. It is essential, however, to ensure that s and goal are of the same length before checking for a sub-string match, as having different lengths automatically implies that no amount of shifting will make the two strings equal.

Solution Approach

The implementation of the solution is quite straightforward and elegant due to the simplicity of the logic involved. It leverages both the Python string methods and the concept of string concatenation and sub-string search. Here's how it's done using the given solution code:

First, the solution checks if s and goal have the same length, as different lengths would make it impossible for s to be shifted into goal. This is done with the expression len(s) == len(goal). If they are not of equal length, the function will return False.
Next, if the lengths are equal, the solution concatenates string s with itself using s + s. This double-length string contains all the possible shifts of string s. For example, for s = "abcde", s + s = "abcdeabcde" would include "eabcd", "deabc", "cdeab", and so on, as its substrings.
The final check is to see if goal is a sub-string within this concatenated version of s. This is achieved with the expression goal in s + s. In Python, the in operator checks if one string is contained within another, returning True if it is found and False if not.

By combining these steps, the function rotateString assesses whether there exists a sequence of shifts that transform s into goal. If goal exists as a sub-string in s + s, that means goal could be reached by shifting s a certain number of times.

In terms of algorithms and data structures, this approach uses a linear search underneath the in operation, and the extra space used is directly proportional to the size of string s due to the concatenation. However, since string concatenation and searching are highly optimized in Python, this solution is both space and time-efficient for the problem at hand.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach for the problem of determining if one string can be transformed into another through cyclic shifts.

Imagine we have s = "abc" and goal = "cab". We want to find out if by cyclically shifting s, we can obtain goal.

First of all, we check if both s and goal have the same length. Here, both s and goal have a length of 3, so we pass this check.
We then concatenate s with itself. So, s + s = "abcabc". Notice that this new string, "abcabc", contains all possible shifts of s:
- The original string "abc" (starting at index 0)
- The first shift "bca" (starting at index 1)
- The second shift "cab" (starting at index 2)
Finally, we look for goal in this new doubled string. goal = "cab" is a substring of s + s = "abcabc", starting from index 2 to index 4.

Because we found goal within s + s, we can confidently return True, which signifies that it is possible to get goal by shifting s two places to the right.

Had goal not been found within the double string s + s, we would have returned False, meaning no amount of shifting would have matched s to goal.

By following these steps with Python's concise string operations, we have a solution that is both elegant and efficient.

Solution Implementation

1class Solution:
2    def rotateString(self, s: str, goal: str) -> bool:
3        # Compare the lengths of the strings to ensure they are the same, 
4        # which is a prerequisite for one to be a rotation of the other.
5        if len(s) != len(goal):
6            return False
7      
8        # Concatenate the string 's' with itself, which covers all possible rotations.
9        # If 'goal' is a rotated version of 's', it will be a substring of 's+s'.
10        # Check if 'goal' is present within this concatenated string.
11        return goal in (s + s)
12
13# Example usage:
14# solution = Solution()
15# result = solution.rotateString("abcde", "cdeab")
16# print(result)  # Output would be True since "cdeab" is a rotation of "abcde"
17

1class Solution {
2    // Method to check if the string 'goal' can be obtained by rotating 's'.
3    public boolean rotateString(String s, String goal) {
4        // Check if the two strings are of the same length.
5        // If they aren't, they cannot be rotations of each other.
6        if (s.length() != goal.length()) {
7            return false;
8        }
9      
10        // Concatenate 's' with itself. In such a string, any rotation of 's'
11        // would appear as a substring.
12        String doubledS = s + s;
13
14        // Check if the concatenated string contains 'goal' as a substring.
15        // If it does, 'goal' is a rotation of 's'.
16        return doubledS.contains(goal);
17    }
18}
19

1#include <string> // Include necessary library for using strings
2#include <cstring> // Include C-string library for strstr function
3
4class Solution {
5public:
6    // Function to check if string 's' after rotation can become string 'goal'
7    bool rotateString(std::string s, std::string goal) {
8        // First check if the sizes of both strings are equal, an essential condition for rotation
9        if (s.size() != goal.size()) {
10            return false; // If sizes differ, one cannot be a rotation of the other
11        }
12
13        // Double the string 's' so that it contains all possible rotations
14        std::string doubled_s = s + s;
15
16        // Use the C library function 'strstr' to check if 'goal' is a substring of 'doubled_s'
17        // 'strstr' returns a pointer to the first occurrence of 'goal' in 'doubled_s', or a null pointer if 'goal' is not present
18        // 'data()' method provides a pointer to the start of the string data
19        return strstr(doubled_s.data(), goal.data()) != nullptr;
20    }
21};
22

1// Checks whether the string 's' can be rotated to match the string 'goal'
2function rotateString(s: string, goal: string): boolean {
3    // Check if the lengths of both strings are equal, as a necessary condition for rotation
4    if (s.length !== goal.length) {
5        return false;
6    }
7  
8    // Concatenate the goal string with itself
9    const doubledGoal = goal + goal;
10  
11    // Check if the original string 's' is a substring of the concatenated string 'doubledGoal'
12    // This would imply that 's' can be rotated to form 'goal'
13    return doubledGoal.includes(s);
14}
15

Time and Space Complexity

The given Python function rotateString checks if s rotated can be equal to goal by appending s to itself and checking if goal is a substring of the result.

Time Complexity

The time complexity of the function is determined primarily by the in operation where goal is checked to be a substring of s + s. In the worst-case scenario, the in statement takes O(n*m) time, where n is the length of the string s and m is the length of the string goal. In this code, since we ensure that len(s) == len(goal), we can simplify this to O(n^2).

However, most modern Python implementations use optimized substring search algorithms like the Boyer-Moore or the Knuth-Morris-Pratt algorithm, which on average can provide sub-linear performance in practice, but for the worst-case analysis, we can consider O(n^2).

Space Complexity

Space complexity is determined by the additional space used by the program beyond the input and output. For this code, creating s + s generates a temporary string that requires O(n) space, where n is the length of s (since s and goal are the same length).

Thus, the space complexity of the function is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know