Derive Strings - C++ Solution

1. Introduction

The "Derive Strings" problem is a string manipulation challenge that focuses on determining if one string can be derived from another through circular rotation. This problem tests understanding of string operations and is a common question in programming interviews.

Problem

Given two strings X and Y, the task is to check if Y can be derived from X by circularly rotating X either clockwise or anti-clockwise. The rotation implies shifting all characters of X by a certain number of positions to the right or left, wrapping around the ends of the string.

2. Solution Steps

1. Check if the lengths of both strings are equal. If not, return false.

2. Concatenate string X with itself. This creates a string that contains all possible rotations of X.

3. Check if string Y is a substring of the concatenated string.

4. If Y is found in the concatenated string, return true; otherwise, return false.

3. Code Program

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

// Function to check if Y can be derived from X by circular rotation
bool isCircularRotation(const string &X, const string &Y) {
    if (X.length() != Y.length()) {
        return false; // Strings of unequal length cannot be rotations of each other
    }

    string temp = X + X; // Concatenate X with itself
    return (temp.find(Y) != string::npos); // Check if Y is a substring of temp
}

int main() {
    string X = "ABCD";
    string Y = "DABC";
    cout << boolalpha << isCircularRotation(X, Y) << endl;
    return 0;
}

Output:

true

Explanation:

The program starts by checking if strings X and Y are of equal length, as rotation is not possible between strings of different lengths. It then concatenates X with itself, forming a string that contains all possible rotations of X. By checking if Y is a substring of this concatenated string, the program efficiently determines if Y can be derived from X through rotation.

 This solution is elegant and efficient, utilizing standard string operations to solve the problem.