LeetCode Entry

796. Rotate String

03.05.2026 easy 2026 kotlin rust

Match strings after rotation

796. Rotate String easy substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1347

Problem TLDR

Match strings after rotation

Intuition

Brute-force: check every possible rotation Clever idea: rotation is identical to repetition, find goal in concatenated source KMP: precompute p[] array where p[i] is the length of matching goal[0..p[i]-1] == goal[i-(p[i]-1)..i]. Jump back j = p[j-1] if chars doesn’t match.

Approach

• the .contains in Rust has O(n) time and O(1) space complexity and based on Two-Way String Matching algo (that is alien looking and based on math

Complexity

• Time complexity: \(O(n^2|n)\)

• Space complexity: \(O(1|n)\)

Code

    fun rotateString(s: String, g: String) =
    s.length==g.length && g in s+s

    pub fn rotate_string(s: String, g: String) -> bool {
        let (s,g) = (s.as_bytes(), g.as_bytes());
        let (mut p, mut j) = (vec![0; g.len()], 0);
        for i in 1..p.len() {
            while j > 0 && g[i] != g[j] { j = p[j-1] }
            if g[i] == g[j] { j += 1}; p[i] = j
        }; j = 0;
        p.len() == s.len() && (0..s.len() * 2).any(|i| {
            while j > 0 && s[i%s.len()] != g[j] { j = p[j-1] }
            if s[i%s.len()] == g[j] { j += 1 }; j == p.len()
        })
    }