Vultr DocsLatest Content

Rotate String

Updated on 25 June, 2025
Rotate String header image

Problem Statement

In this problem, we are given two strings, s and goal. Our task is to determine if s can be transformed into goal through a series of circular shifts. A circular shift involves taking the first character of string s and moving it to the end of the string. For example, shifting "abcde" one time results in "bcdea." We need to ascertain if by repeatedly applying this operation, s could ever match goal.

Examples

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.

Approach and Intuition

To determine whether string s can be transformed into goal by performing several shifts, we can use the following approach:

  1. Check Length: First, ensure that s and goal are of the same length. If they are not, returning false is immediate since the differing lengths imply unequal strings regardless of shifting.

  2. Concatenate and Check: A clever trick to check for a possible circular shift is to consider the string s appended to itself. This new string, s + s, contains all possible shifts of s within it as substrates. For example, "abcdeabcde" (which is "abcde" + "abcde") contains "deabc", "cdeab", etc., as its substrates.

  3. Find Substring: Check if goal is a substring of this concatenated string s + s. If goal exists as a substring, then one of the shifts of s aligns perfectly with goal, thereby making it possible to transform s into goal through shifts.

By using this method, we avoid the inefficiency of manually shifting the string up to potentially its length times and checking equality after every shift. Instead, the substring method leverages existing efficient algorithms in most programming languages to check for substrings quickly.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    bool canRotateToMatch(string original, string target) {
        // Verify lengths
        if (original.size() != target.size()) return false;

        // Double the original string to encompass all possible rotations
        string extended = original + original;

        // Verify if 'target' is within 'extended' using string search
        return substringSearch(extended, target);
    }

private:
    bool substringSearch(const string& text, const string& pattern) {
        // Compute LPS array for pattern
        vector<int> lps = prepareLPS(pattern);
        int textIdx = 0, patternIdx = 0;
        int textLen = text.size(), patternLen = pattern.size();

        // Search using KMP algorithm
        while (textIdx < textLen) {
            if (text[textIdx] == pattern[patternIdx]) {
                textIdx++;
                patternIdx++;
                if (patternIdx == patternLen) return true;
            } else if (patternIdx > 0) {
                patternIdx = lps[patternIdx - 1];
            } else {
                textIdx++;
            }
        }
        return false;
    }

    vector<int> prepareLPS(const string& pattern) {
        int len = pattern.size();
        vector<int> lps(len, 0);
        int l = 0, i = 1;

        // Construct LPS for pattern
        while (i < len) {
            if (pattern[i] == pattern[l]) {
                l++;
                lps[i++] = l;
            } else if (l > 0) {
                l = lps[l - 1];
            } else {
                lps[i++] = 0;
            }
        }
        return lps;
    }
};

This C++ solution addresses the problem of determining if one string is a rotation of another string by leveraging the Knuth-Morris-Pratt (KMP) substring search algorithm. The method canRotateToMatch first checks if both the original and target strings are of the same length. If not, it returns false since rotation is not possible.

If the lengths match, the solution concatenates the original string with itself, creating an extended version that includes all possible rotations as its substrings. The program then searches to see if the target string exists within this extended string.

The core of the algorithm lies in the substringSearch function, which implements the KMP algorithm to efficiently search for the target string within the extended string. KMP algorithm improves the search time by using a preprocessing step that creates a Longest Prefix Suffix (LPS) array. The prepareLPS function builds this array, which helps in reducing the time complexity of the search by skipping unnecessary comparisons.

  • The prepareLPS function constructs the LPS array based on the pattern, allowing the search to jump over characters that have already been matched.
  • The substringSearch function uses the LPS array to search through the text and checks if the pattern (target string) is found.

Through this method, the solution verifies the existence of the target string within the concatenated string, effectively determining if one string is a rotation of the other.

java 
class Solution {

    public boolean canRotate(String org, String rotGoal) {
        // Checking if string lengths are unequal
        if (org.length() != rotGoal.length()) return false;

        // Create a doubled version of original string
        String doubleOrg = org + org;
        
        // Check if rotated goal is a part of this new double string
        return isSubstring(doubleOrg, rotGoal);
    }

    private boolean isSubstring(String fullText, String subText) {
        // Building LPS array for the subText
        int[] lpsArray = buildLPS(subText);
        int mainIndex = 0, subIndex = 0;
        int mainLength = fullText.length(), subLength = subText.length();

        // Iterating over the fullText
        while (mainIndex < mainLength) {
            // Matching characters move indices forward
            if (fullText.charAt(mainIndex) == subText.charAt(subIndex)) {
                mainIndex++;
                subIndex++;
                // Complete substring match
                if (subIndex == subLength) return true;
            } 
            // Utilizing LPS array to skip unnecessary checks
            else if (subIndex > 0) {
                subIndex = lpsArray[subIndex - 1];
            }
            // Progress mainIndex in absence of matches
            else {
                mainIndex++;
            }
        }
        // No successful substring match found
        return false;
    }

    private int[] buildLPS(String substring) {
        int subLen = substring.length();
        int[] lps = new int[subLen];
        int len = 0, i = 1;

        // Constructing the LPS array
        while (i < subLen) {
            // Extend match length
            if (substring.charAt(i) == substring.charAt(len)) {
                len++;
                lps[i++] = len;
            }
            // Proceed with LPS logic to improve efficiency
            else if (len > 0) {
                len = lps[len - 1];
            }
            // No match extension possible
            else {
                lps[i++] = 0;
            }
        }
        return lps;
    }
}

The Java solution for the "Rotate String" problem checks if one string is a rotation of another using a string manipulation and substring search approach. First, the solution verifies if the two strings, org and rotGoal, are of the same length, as different lengths immediately invalidate any possibility of one being a rotation of the other.

Upon confirming the lengths are equal, the algorithm concatenates the original string org with itself, resulting in doubleOrg. The idea behind this step is that any rotation of the original string would appear as a substring of this double version. For instance, for the string "abc", "abcabc" will contain all possible rotations ("abc", "bca", "cab").

The solution then leverages a helper method, isSubstring, to determine if rotGoal is contained within doubleOrg. This method uses the Knuth-Morris-Pratt (KMP) algorithm to efficiently find if rotGoal is a substring without rechecking previously matched characters after a mismatch. This is achieved through the construction and utilization of the Longest Prefix Suffix (LPS) array, which stores the lengths of the longest prefix which is also a suffix for every prefix of rotGoal.

If isSubstring finds that rotGoal is indeed part of doubleOrg, the method returns true, confirming that one string is a rotation of the other. If not, it returns false. Thus, you can quickly and efficiently determine string rotations with this approach.

  • Highlights:
    • Checks initial string length equality to ensure that rotation is feasible.
    • Constructs a doubled version of the original string to encapsulate all possible rotations.
    • Employs the KMP algorithm for efficient substring searching, minimizing unnecessary checks and re-evaluations.
python 
class Solution:
    def canRotate(self, original: str, target: str) -> bool:
        if len(original) != len(target):
            return False

        combined = original + original
        return self.substringSearch(combined, target)

    def substringSearch(self, haystack: str, needle: str) -> bool:
        lps = self.computeLPSArray(needle)
        i = j = 0
        lenHaystack = len(haystack)
        lenNeedle = len(needle)

        while i < lenHaystack:
            if haystack[i] == needle[j]:
                i += 1
                j += 1
                if j == lenNeedle:
                    return True
            elif j > 0:
                j = lps[j - 1]
            else:
                i += 1
        return False

    def computeLPSArray(self, pat: str) -> list:
        l = len(pat)
        lps = [0] * l
        lenLPS = 0
        i = 1

        while i < l:
            if pat[i] == pat[lenLPS]:
                lenLPS += 1
                lps[i] = lenLPS
                i += 1
            elif lenLPS > 0:
                lenLPS = lps[lenLPS - 1]
            else:
                lps[i] = 0
                i += 1

        return lps

The provided Python code defines a Solution class that checks if one string is a rotation of another. The process is encapsulated in three main methods:

  1. canRotate: This method first checks if the two strings, original and target, have the same length, immediately returning False if they do not. If they are the same length, it then appends original to itself and searches for target within this new string using the substringSearch method.

  • substringSearch: This method implements a modified version of the Knuth-Morris-Pratt (KMP) search algorithm for substring search. It uses a helper method called computeLPSArray to preprocess the target string to create an LPS (longest prefix suffix) array. The algorithm efficiently determines if target is a substring of the concatenated string (original+original).

  • computeLPSArray: This method computes the LPS array for the KMP algorithm. The LPS array contains values that help in skipping unnecessary comparisons when a mismatch occurs during the KMP search process.

By leveraging the KMP algorithm, the approach ensures efficient checking of whether one string is a rotation of another by avoiding naive string matching, which would significantly increase the computational cost for large string inputs. This solution is particularly effective as it smartly checks rotations by searching within a double-length string variant, rather than creating and comparing all possible rotations explicitly.

Comments

No comments yet.