algoadvance

Leetcode 796. Rotate String

Problem Statement

Leetcode 796: Rotate String

We are given two strings s and goal. We need to determine if s can become goal after a series of shifts. In one shift, s is moved to the left by one position. For example, if s = "abcde", then it can be shifted to the left to become "bcdea", "cdeab", "deabc", "eabcd", and finally back to "abcde".

Clarifying Questions

  1. What are the constraints on the lengths of s and goal?
    • Both strings have a length ranging from 1 to 100.
  2. Are there any specific characters allowed in the strings?
    • The strings consist of lowercase English letters.
  3. Can the strings be of different lengths?
    • No, for s to possibly be rotated into goal, both strings need to be of the same length.

Strategy

To determine if s can become goal after a series of shifts:

  1. Concatenate s with itself: This would allow us to check for any shifted versions within the new string.
  2. Check for substring: If goal is a substring within the concatenated string, then s can be shifted to become goal.

Code

public class Solution {
    public boolean rotateString(String s, String goal) {
        if (s.length() != goal.length()) {
            return false;
        }
        String concatenated = s + s;
        return concatenated.contains(goal);
    }
}

Explanation

  1. Checking Length: First, we check if s and goal have the same length. If not, return false since they cannot be the same string after any number of shifts.
  2. Concatenate and Check: We concatenate s with itself to create a new string. If goal is a substring of this new string, it means that goal can be formed by rotating s.

Time Complexity

  1. Concatenation: Concatenating s with itself takes O(n) time where n is the length of s.
  2. Substring Check: Checking if goal is a substring in the concatenated string can be performed in O(n) time typically (char checking would take linear time given efficient implementations).

Thus, the overall time complexity is O(n) where n is the length of the strings s and goal.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI