algoadvance

Leetcode Problem 796: Rotate String

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

Clarifying Questions

1. What is the length constraint on the strings s and goal?
2. Do both strings need to be of the same length?
3. Are the strings guaranteed to contain only lowercase letters?
4. What should we return if either s or goal is empty?

Strategy

1. Length Check: First, check if the lengths of s and goal are different. If they are, return False because a string cannot be rotated into another string of a different length.
2. Concatenation Method: Concatenate s with itself (i.e., s + s). This will include all possible rotations of s as substrings.
3. Substring Check: Check if goal is a substring of the concatenated string s + s.

Time Complexity

• Performing the concatenation takes (O(n)) where (n) is the length of the string s.
• Checking if goal is a substring of s + s will take (O(n)) on average assuming efficient substring search algorithms.

So, the overall time complexity is (O(n)).

Code

def rotateString(s: str, goal: str) -> bool:
    if len(s) != len(goal):
        return False

    concatenated_s = s + s
    return goal in concatenated_s

Here is how the solution works:

1. It checks if the lengths of s and goal are the same.
2. If they are, it concatenates s with itself to form a new string concatenated_s.
3. It checks if goal is a substring of concatenated_s, and returns True if it is, otherwise False.

This method ensures an efficient check for all rotations of s within a linear time complexity.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?