Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Rotate String | Leetcode 796 | Optimal Substring Search Solution
    Data Structures & Algorithms

    Rotate String | Leetcode 796 | Optimal Substring Search Solution

    codeanddebugBy codeanddebug1 September 2025No Comments2 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Featured image of a question to solve Rotate String
    Share
    Facebook Twitter LinkedIn Pinterest Email

    The Rotate String problem asks us to check whether one string goal can be obtained by rotating another string s.

    • A rotation means repeatedly moving the leftmost character of a string to the rightmost position.
    • We need to return True if after some number of rotations, s can become goal; otherwise return False.

    Here’s the [Problem Link] to begin with.


    Examples

    Example 1

    Input: s = "abcde", goal = "cdeab"
    Output: true
    Explanation: "abcde" → "bcdea" → "cdeab"

    Example 2

    Input: s = "abcde", goal = "abced"
    Output: false
    Explanation: No rotation of "abcde" equals "abced".

    Intuition and Approach

    To solve Rotate String, let’s analyze:

    1. Rotation property:
      • If you rotate a string s, the result is always a substring of s+s.
      • Example: s = "abcde" → s+s = "abcdeabcde".
        • All possible rotations ("abcde", "bcdea", "cdeab", "deabc", "eabcd") are substrings of "abcdeabcde".
    2. Algorithm:
      • Check if lengths of s and goal are equal. If not, return False.
      • Create string = s + s.
      • If goal is a substring of string, return True. Otherwise return False.

    This trick is both simple and optimal, avoiding the need to simulate rotations.


    Code Implementation

    class Solution:
        def rotateString(self, s: str, goal: str) -> bool:
            if len(s) != len(goal):
                return False
            string = s + s
            return goal in string

    Code Explanation

    1. Length check:
      • If s and goal have different lengths, rotation is impossible.
    2. Concatenate string:
      • s + s contains all possible rotations of s.
    3. Substring check:
      • If goal is in s+s, then goal is a valid rotation.
      • Otherwise, return False.

    Dry Run

    Input: s = "abcde", goal = "cdeab"

    • Check lengths: both length = 5 → valid.
    • Concatenate: "abcde" + "abcde" = "abcdeabcde".
    • Check substring: "cdeab" in "abcdeabcde" → True.

    Output: True.


    Time and Space Complexity

    • Time Complexity:
      • Concatenation takes O(N).
      • Substring search takes O(N) (average, depending on implementation).
        Overall: O(N), where N is the length of the string.
    • Space Complexity:
      • We create s+s, which takes O(N) extra space.

    Conclusion

    The Rotate String problem can be solved optimally using the property that all rotations of a string appear as substrings of s+s.

    • Avoids explicit rotation simulation.
    • Runs in O(N) time and space.
    • Clean and elegant one-liner:
    return len(s) == len(goal) and goal in (s+s)

    This solution is both interview-friendly and competitive programming optimal.


    Join our Advance DSA COURSE

    For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.

    Easy Strings
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleIsomorphic Strings | Leetcode 205 | Optimal Hash Map Solution
    Next Article Valid Anagram | Leetcode 242 | Optimal Hash Map Solution
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Symmetric Tree | Leetcode 101 | Recursive DFS Approach

    2 September 2025
    Data Structures & Algorithms

    Binary Tree Right Side View | Leetcode 199 | BFS and DFS Approaches

    2 September 2025
    Data Structures & Algorithms

    Bottom View of Binary Tree | BFS with Horizontal Distance Mapping

    2 September 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (240)
      • Beginner (82)
      • Expert (52)
      • Intermediate (106)
    • Uncategorised (1)
    Recent Posts

    Symmetric Tree | Leetcode 101 | Recursive DFS Approach

    2 September 2025

    Binary Tree Right Side View | Leetcode 199 | BFS and DFS Approaches

    2 September 2025

    Bottom View of Binary Tree | BFS with Horizontal Distance Mapping

    2 September 2025

    Top View of Binary Tree | BFS with Horizontal Distance Mapping

    2 September 2025

    Vertical Order Traversal of a Binary Tree | Leetcode 987 | BFS + Sorting Solution

    2 September 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.