Java: Find all interleavings of specified strings

Last update on December 21 2024 10:02:38 (UTC/GMT +8 hours)

Write a Java program to find all interleavings of given strings.

Sample Solution:

Java Code:

// Import necessary Java utilities.
import java.util.HashSet;
import java.util.Set;

// Define a class named Main.
class Main {
    
    // Define a method to find all interleavings of two strings.
    public static void allInterleavings(String res, String P, String Q, Set out) {
        // If both strings are empty, add the result to the output set.
        if (P.length() == 0 && Q.length() == 0) {
            out.add(res);
            return;
        }
        
        // If string P is not empty, recursively call allInterleavings with the first character of P removed.
        if (P.length() > 0) {
            allInterleavings(res + P.charAt(0), P.substring(1), Q, out);
        }
        
        // If string Q is not empty, recursively call allInterleavings with the first character of Q removed.
        if (Q.length() > 0) {
            allInterleavings(res + Q.charAt(0), P, Q.substring(1), out);
        }
    }

    // The main method to execute the code.
    public static void main(String[] args) {
        // Define the input strings.
        String P = "WX";
        String Q = "YZ";

        // Print the given strings.
        System.out.println("The given strings are: " + P + "  " + Q);
        System.out.println("The interleavings strings are: ");

        // Create a HashSet to store unique interleavings.
        Set<String> out = new HashSet<>();

        // Call the allInterleavings method to generate interleavings of the input strings.
        allInterleavings("", P, Q, out);

        // Print all the generated interleavings using streams.
        out.stream().forEach(System.out::println);
    }
}

Sample Output:

The given strings are: WX  YZ
The interleavings strings are: 
YWZX
WYZX
YWXZ
WXYZ
YZWX
WYXZ

Flowchart:

Java Code Editor:

Improve this sample solution and post your code through Disqus

Previous: Write a Java program to find longest Palindromic Substring within a string.
Next: Write a Java program to find the second most frequent character in a given string.