Jobs

Interviews

Discussions

Rotate String

Easy

SAP

3 views

Topics:

Strings

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.

Try coding it in LeetCode

Rotate String

Easy

SAP

3 views

Topics:

Strings

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can s or goal be empty strings or null?
Are s and goal guaranteed to be of the same length? If they aren't, can s possibly be rotated to match goal?
Are there any constraints on the characters that s and goal can contain? (e.g., ASCII, Unicode)
Is case sensitivity important? Should I consider 'abc' and 'bca' as a rotation of 'ABC' and 'BCA'?
If s and goal are identical strings, should I return true?

Brute Force Solution

Approach

The goal is to see if one string can become another by shifting its characters around. The brute force method involves trying every possible shift to see if any of them match the target string.

Here's how the algorithm would work step-by-step:

Imagine taking the first string and moving its first letter to the very end.
Check if this new string is identical to the second string.
If it is, you're done! The second string is just a rotated version of the first.
If it isn't, take the first letter of this new string and move it to the end again.
Keep doing this shifting and comparing, one letter at a time, until you've tried every possible shift.
If you've gone through every shift and none of them match the second string, then it's not a rotated version.

Code Implementation

def rotate_string_brute_force(first_string, second_string):
    string_length = len(first_string)

    # Strings of different lengths can't be rotations of each other
    if len(second_string) != string_length:
        return False

    for shift_amount in range(string_length):
        # Perform the rotation
        rotated_string = first_string[shift_amount:] + first_string[:shift_amount]

        # Check if the rotated string matches the target
        if rotated_string == second_string:
            return True

    # If no rotation matches, return False
    return False

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates up to n times, where n is the length of the string, performing rotations. Within each iteration, it compares the rotated string with the target string, which takes O(n) time. Thus, the time complexity is dominated by n rotations, each involving an O(n) comparison, resulting in O(n * n) operations. Therefore, the time complexity of the brute force approach is O(n²).

Space Complexity

O(1) – The provided algorithm operates by repeatedly shifting characters within a string and comparing it to another. This shifting is typically done in-place or by creating a single temporary string to hold the shifted version, however, the plain English description does not imply an additional data structure is needed of size N. Only a few variables are used for comparison and shifting. Therefore, the space complexity is constant and does not depend on the input string length N.

Optimal Solution

Approach

The key insight is that if one string is a rotation of another, it must exist as a substring within the doubled version of the original string. We create a longer string, and then perform a single search.

Here's how the algorithm would work step-by-step:

Take the original string and duplicate it, creating a new string that's twice as long.
Check if the rotated string exists within this doubled string.
If the rotated string is found within the doubled string, then it is a rotation of the original string; otherwise, it is not.

Code Implementation

def rotate_string(original_string, rotated_string):
    # Check for edge cases where rotation is impossible
    if len(original_string) != len(rotated_string):
        return False

    doubled_original_string = original_string + original_string

    # If rotated_string is a rotation, it must be a substring
    if rotated_string in doubled_original_string:
        return True

    return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm involves creating a doubled string, which takes O(n) time where n is the length of the original string. The core operation is searching for the rotated string within the doubled string using a string search algorithm. Efficient string search algorithms like the Knuth-Morris-Pratt (KMP) algorithm or Boyer-Moore algorithm can perform this search in O(n) time. Therefore, the overall time complexity is dominated by the string creation and search, both taking O(n) time, resulting in a total time complexity of O(n).

Space Complexity

O(N) – The primary space usage comes from creating the doubled string, which requires a new string of length 2N, where N is the length of the original string. The doubled string stores characters and thus consumes memory proportional to its length. The other operations like string searching use minimal extra space. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Both s and goal are null or empty strings	Return true since an empty string can be considered a shifted version of itself.
s is null or empty, but goal is not (or vice-versa)	Return false since an empty string cannot be shifted to a non-empty string.
s and goal have different lengths	Return false because strings of different lengths cannot be rotations of each other.
s and goal are identical strings	Return true because a string is a rotation of itself (zero shifts).
s and goal are very long strings (performance implications)	Ensure solution has linear time complexity (e.g., by checking if goal is a substring of s+s).
s contains repeated characters, and goal contains the same characters but in a rotated order.	The substring check will correctly identify the rotation in linear time.
s and goal are anagrams of each other but not rotations	The substring check `goal in s + s` will not identify anagrams as rotations; it requires the specific shifted sequence.
Very large strings causing memory issues if s+s is created.	Consider using rolling hash or KMP algorithm for substring search, avoiding string concatenation and minimizing memory usage.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can s or goal be empty strings or null?
Are s and goal guaranteed to be of the same length? If they aren't, can s possibly be rotated to match goal?
Are there any constraints on the characters that s and goal can contain? (e.g., ASCII, Unicode)
Is case sensitivity important? Should I consider 'abc' and 'bca' as a rotation of 'ABC' and 'BCA'?
If s and goal are identical strings, should I return true?

Brute Force Solution

Approach

The goal is to see if one string can become another by shifting its characters around. The brute force method involves trying every possible shift to see if any of them match the target string.

Here's how the algorithm would work step-by-step:

Imagine taking the first string and moving its first letter to the very end.
Check if this new string is identical to the second string.
If it is, you're done! The second string is just a rotated version of the first.
If it isn't, take the first letter of this new string and move it to the end again.
Keep doing this shifting and comparing, one letter at a time, until you've tried every possible shift.
If you've gone through every shift and none of them match the second string, then it's not a rotated version.

Code Implementation

def rotate_string_brute_force(first_string, second_string):
    string_length = len(first_string)

    # Strings of different lengths can't be rotations of each other
    if len(second_string) != string_length:
        return False

    for shift_amount in range(string_length):
        # Perform the rotation
        rotated_string = first_string[shift_amount:] + first_string[:shift_amount]

        # Check if the rotated string matches the target
        if rotated_string == second_string:
            return True

    # If no rotation matches, return False
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Take the original string and duplicate it, creating a new string that's twice as long.
Check if the rotated string exists within this doubled string.
If the rotated string is found within the doubled string, then it is a rotation of the original string; otherwise, it is not.

Code Implementation

def rotate_string(original_string, rotated_string):
    # Check for edge cases where rotation is impossible
    if len(original_string) != len(rotated_string):
        return False

    doubled_original_string = original_string + original_string

    # If rotated_string is a rotation, it must be a substring
    if rotated_string in doubled_original_string:
        return True

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both s and goal are null or empty strings	Return true since an empty string can be considered a shifted version of itself.
s is null or empty, but goal is not (or vice-versa)	Return false since an empty string cannot be shifted to a non-empty string.
s and goal have different lengths	Return false because strings of different lengths cannot be rotations of each other.
s and goal are identical strings	Return true because a string is a rotation of itself (zero shifts).
s and goal are very long strings (performance implications)	Ensure solution has linear time complexity (e.g., by checking if goal is a substring of s+s).
s contains repeated characters, and goal contains the same characters but in a rotated order.	The substring check will correctly identify the rotation in linear time.
s and goal are anagrams of each other but not rotations	The substring check `goal in s + s` will not identify anagrams as rotations; it requires the specific shifted sequence.
Very large strings causing memory issues if s+s is created.	Consider using rolling hash or KMP algorithm for substring search, avoiding string concatenation and minimizing memory usage.