Java Program to Check if Two Strings are Cyclic Permutations of Each Other

It is a question that is usually asked in job interviews at prestigious IT companies such as Google, Microsoft, TCS, Accenture, etc. By figuring out the solution, one may assess the interviewee's logical reasoning, critical thinking, & problem-solving abilities. In this section we will create a Java program to check if two strings of the same length are cyclical permutations of one each other or not using different approaches.

Cyclic Permutation

A circular permutation occurs when a string can be changed into another by spinning its characters.

Example:

• String str1 = "ABCD";
• String str2 = "CDAB";

Output:

• Yes (since rotating "CDAB" gives "ABCD")

There are various approaches to check if two strings are cyclic permutations of each other or not. In this section, we will discuss the approaches give below:

1. Sorting and Comparison Approach
2. Counting and Comparison Approach
3. Single Array Counting Approaches

Using Sorting and Comparison Approach

Sorting and Comparison is an approach where two strings are first converted into character arrays, then sorted and compared. If the sorted arrays match, the strings are considered permutations of each other.

Let's implement the above approach in a Java program.

File Name: PermutationChecker.java

Output:

 
No   

Time Complexity: O(n log n)

Auxiliary Space: O(n)

Using Counting and Comparison Approach

Counting and Comparison is an approach where character frequencies in both strings are counted using arrays. These frequency arrays are then compared to determine if the strings are permutations of each other.

Let's implement the above approach in a Java program.

File Name: PermutationChecker.java

Output:

 
Yes   

Time Complexity: O(n), where n is the length of the strings.

Auxiliary Space: O(1)

Using Single Array Counting Approach

The approach uses a single array to track the frequency of characters in both strings. It ensures the strings are permutations by checking if their character counts match after processing.

File Name: PermutationChecker.java

Output:

 
Yes