algoadvance

Leetcode 796. Rotate String

Problem Statement

The LeetCode problem 796 - “Rotate String” is defined as follows:

Given two strings s and goal, return true if and only if s can become goal after some number of shifts on s.

A shift on s consists of moving the leftmost character of s to the rightmost position. For example, if s = 'abcde', then it will be 'bcdea' after one shift.

Clarifying Questions

  1. What are the constraints on the length of the strings s and goal?
    • Both strings can have 1 ≤ s.length ≤ 100.
  2. What characters are valid in the strings s and goal?
    • The strings can consist of lowercase English letters only.
  3. Is there an edge case where s or goal can be empty?
    • No, based on the constraints, s and goal must have at least one character.
  4. Is it guaranteed that s and goal will be of equal length?
    • No, s and goal can have different lengths.

Strategy

To solve this problem, the main idea is to check if goal can be obtained by rotating s. If two strings are of different lengths, they cannot be rotations of each other. Otherwise, we can concatenate s with itself (i.e., s + s), and check if goal is a substring of this concatenated string.

This works because concatenating s with itself essentially covers all possible rotations within its structure. For example, for s = 'abcde', concatenating it with itself gives 'abcdeabcde'. The goal string needs to be a substring of this new string to be a valid rotation.

Code

#include <string>

class Solution {
public:
    bool rotateString(std::string s, std::string goal) {
        if (s.length() != goal.length()) {
            return false;
        }
        std::string concatenated = s + s;
        return (concatenated.find(goal) != std::string::npos);
    }
};

Explanation

  1. Length Check: First, check if the lengths of s and goal are different. If they are, return false since they cannot be rotations of each other.
  2. Concatenation: Concatenate s with itself to cover all possible rotations.
  3. Substring Check: Use the find function to check if goal is a substring of the concatenated string.

Time Complexity

This efficient approach ensures that the problem is solved within acceptable limits for given constraints.

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