Solution 1 - Brute Force (Check All Rotations)

A shift on s moves the leftmost character to the rightmost position. We can try all n possible rotations of s and check if any matches goal. For each rotation index i, we build the rotated string by slicing s[i:] + s[:i] and compare it to goal.

TimeComplexity: O(n^2)

SpaceComplexity: O(n)

""" 0796.1 - Rotate String - Solution 1 - Brute Force (Check All Rotations) """

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def rotateString(self, s: str, goal: str) -> bool:
        """Rotate String Function"""
        if len(s) != len(goal):
            return False
        for i in range(len(s)):
            if s[i:] + s[:i] == goal:
                return True
        return False


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().rotateString("abcde", "cdeab"))   # True
    print(Solution().rotateString("abcde", "abced"))   # False
    print(Solution().rotateString("a", "a"))           # True
    print(Solution().rotateString("aa", "a"))           # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

/** 0796 - Runnable implementation */

/////////////////////////////////////////////////////////////////////////////////////
// Solution and tests
/////////////////////////////////////////////////////////////////////////////////////
function solve(s,g){return s.length===g.length&&(s+s).includes(g)}
console.log(solve('abcde','cdeab'));

/** 0796 - Runnable implementation */

/////////////////////////////////////////////////////////////////////////////////////
// Solution and tests
/////////////////////////////////////////////////////////////////////////////////////
function solve(s,g){return s.length===g.length&&(s+s).includes(g)}
console.log(solve('abcde','cdeab'));

// 0796 - Runnable implementation

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import ("fmt";"sort";"strings")

/////////////////////////////////////////////////////////////////////////////////////
// Solution and Main
/////////////////////////////////////////////////////////////////////////////////////
func solve(s,g string) bool{return len(s)==len(g)&&strings.Contains(s+s,g)}
func main(){fmt.Println(solve("abcde","cdeab"))}

// 0796 - Runnable implementation

/////////////////////////////////////////////////////////////////////////////////////
// Solution and Main
/////////////////////////////////////////////////////////////////////////////////////
fn solve(s:&str,g:&str)->bool{s.len()==g.len()&&format!("{}{}",s,s).contains(g)}fn main(){println!("{}",solve("abcde","cdeab"));}

Solution 2 - String Concatenation (Optimal)

Key insight: if you concatenate s with itself (s + s), the resulting string contains every possible rotation of s as a substring. So we just check if goal is a substring of s + s (after verifying lengths match). This reduces the problem to a simple substring search.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0796.2 - Rotate String - Solution 2 - String Concatenation (Optimal) """

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def rotateString(self, s: str, goal: str) -> bool:
        """Rotate String Function"""
        return len(s) == len(goal) and goal in s + s


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().rotateString("abcde", "cdeab"))   # True
    print(Solution().rotateString("abcde", "abced"))   # False
    print(Solution().rotateString("a", "a"))           # True
    print(Solution().rotateString("aa", "a"))           # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

/** 0796 - Runnable implementation */

/////////////////////////////////////////////////////////////////////////////////////
// Solution and tests
/////////////////////////////////////////////////////////////////////////////////////
function solve(s,g){return s.length===g.length&&(s+s).includes(g)}
console.log(solve('abcde','cdeab'));

/** 0796 - Runnable implementation */

/////////////////////////////////////////////////////////////////////////////////////
// Solution and tests
/////////////////////////////////////////////////////////////////////////////////////
function solve(s,g){return s.length===g.length&&(s+s).includes(g)}
console.log(solve('abcde','cdeab'));

// 0796 - Runnable implementation

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import ("fmt";"sort";"strings")

/////////////////////////////////////////////////////////////////////////////////////
// Solution and Main
/////////////////////////////////////////////////////////////////////////////////////
func solve(s,g string) bool{return len(s)==len(g)&&strings.Contains(s+s,g)}
func main(){fmt.Println(solve("abcde","cdeab"))}

// 0796 - Runnable implementation

/////////////////////////////////////////////////////////////////////////////////////
// Solution and Main
/////////////////////////////////////////////////////////////////////////////////////
fn solve(s:&str,g:&str)->bool{s.len()==g.len()&&format!("{}{}",s,s).contains(g)}fn main(){println!("{}",solve("abcde","cdeab"));}

0796 - Rotate String

Solution 1 - Brute Force (Check All Rotations)

Solution 2 - String Concatenation (Optimal)