Table of contents

Check if a string is rotated by K places

Given two strings, s1 and s2, and an integer k, check if s2 is a rotation of s1 by exactly k places. A string rotation by k places means shifting all characters to the left or right by k positions.

Input/Output Examples

plaintext
Example 1:
Input:
s1 = "abcdef"
s2 = "defabc"
k = 3
Output: True
Explanation: Rotating abcdef to the right by 3 places results in defabc, which matches s2.

Example 2:
Input:
s1 = "rotation"
s2 = "tationro"
k = 2
Output: True
Explanation: Rotating rotation to the left by 2 places results in tationro, which matches s2.

Example 3:
Input:
s1 = "example"
s2 = "ampleex"
k = 3
Output: False
Explanation: No rotation of example by exactly 3 places matches s2.

Approach to Check if String is Rotated by K Places

  1. Check for Left Rotation:
    • For a left rotation by k places, the result should match s2 if s1[k:] + s1[:k] is equal to s2.
  2. Check for Right Rotation:
    • For a right rotation by k places, the result should match s2 if s1[-k:] + s1[:-k] is equal to s2.
  3. Return True if Either Condition is Met:
    • If either the left rotation or right rotation of s1 matches s2, return True. Otherwise, return False.

C++ Program to Check if String is Rotated by K Places

cpp
#include <iostream>
#include <string>
using namespace std;

// Function to check if s2 is a rotation of s1 by k places
bool isRotatedByKPlaces(const string& s1, const string& s2, int k) {
    if (s1.length() != s2.length()) return false;

    string leftRot = s1.substr(k) + s1.substr(0, k);
    string rightRot = s1.substr(s1.size() - k) + s1.substr(0, s1.size() - k);

    return (s2 == leftRot || s2 == rightRot);
}

int main() {
    string s1 = "abcdef";
    string s2 = "defabc";
    int k = 3;
    bool result = isRotatedByKPlaces(s1, s2, k);

    cout << (result ? "True" : "False") << endl;
    return 0;
}

Java Program to Check if String is Rotated by K Places

java
public class StringRotationByKPlaces {

    // Function to check if s2 is a rotation of s1 by k places
    public static boolean isRotatedByKPlaces(String s1, String s2, int k) {
        if (s1.length() != s2.length()) return false;

        String leftRot = s1.substring(k) + s1.substring(0, k);
        String rightRot = s1.substring(s1.length() - k) + s1.substring(0, s1.length() - k);

        return s2.equals(leftRot) || s2.equals(rightRot);
    }

    public static void main(String[] args) {
        String s1 = "rotation";
        String s2 = "tationro";
        int k = 2;
        boolean result = isRotatedByKPlaces(s1, s2, k);

        System.out.println(result ? "True" : "False");
    }
}

Python Program to Check if String is Rotated by K Places

python
# Function to check if s2 is a rotation of s1 by k places
def is_rotated_by_k_places(s1, s2, k):
    if len(s1) != len(s2):
        return False

    left_rot = s1[k:] + s1[:k]
    right_rot = s1[-k:] + s1[:-k]

    return s2 == left_rot or s2 == right_rot

# Example usage
if __name__ == "__main__":
    s1 = "example"
    s2 = "ampleex"
    k = 3
    result = is_rotated_by_k_places(s1, s2, k)
    print("True" if result else "False")
  • Time Complexity: O(n), where n is the length of the strings, since slicing or substring operations take linear time relative to the string length.
  • Space Complexity: O(n), as the rotation operations create new substrings or slices that require additional space.

DSA

Related Articles