Check If One String Can Be Rotated Into Another Using TypeScript

Efficiently Check If One String Is a Shifted Version of Another

Problem

Given two strings A and B, return whether or not A can be shifted some number of times to get B.

For example, if A is abcde and B is cdeab, return true. If A is abc and B is acb, return false.

Problem Breakdown

We are given two strings A and B, and we need to check if A can be shifted (rotated) a certain number of times to get B.

Example

  • A = “abcde” and B = “cdeab” → return true because "abcde" can be shifted to form "cdeab".
  • A = “abc” and B = “acb” → return false because no shift will make "abc" become "acb".

Approach

Length Check: First, if the lengths of A and B are different, it’s impossible for one string to be a shifted version of the other.

String Rotation Insight: If we concatenate A with itself (i.e., A + A), all possible rotations of A will be present as a substring within this new string. For example:

  • A = “abcde”
  • A + A = “abcdeabcde” The string “cdeab” will be a substring of “abcdeabcde”.

Solution: If B is a substring of A + A, then B is a rotation of A.

Code Implementation

function canBeShifted(A: string, B: string): boolean {
    // Check if the lengths of A and B are different
    if (A.length !== B.length) {
        return false;
    }

    // Concatenate A with itself
    const doubleA = A + A;

    // Check if B is a substring of doubleA
    return doubleA.includes(B);
}

Explanation:

Length Check: If A and B don’t have the same length, return false immediately because it’s impossible for A to be shifted to form B.

Concatenation: Concatenate A with itself, resulting in a string that contains all possible rotations of A.

Substring Check: If B is found within the concatenated string, A can be shifted to form B, so return true. Otherwise, return false.

Example Walkthrough:

Input: A = “abcde”, B = “cdeab”

  • doubleA = "abcdeabcde"
  • Check if “cdeab” is a substring of “abcdeabcde” → Yes → return true.

Input: A = “abc”, B = “acb”

  • doubleA = "abcabc"
  • Check if “acb” is a substring of “abcabc” → No → return false.

Time Complexity:

Time Complexity: O(n) where n is the length of string A (or B), because the most time-consuming operation is checking for the presence of B as a substring of A + A. Space Complexity: O(n) due to the concatenation of A with itself.

Alternative Approach:

You could manually perform rotations and check each one, but this approach would be less efficient (O(n²) time complexity) than the string concatenation method.

If you like this, please think about buying me a coffee! ☕️.

Burhanuddin’s Code Compendium

Thank you for being a part of the Burhanuddin’s Code Compendium community! Before you go: