Java Program to Check if a string is a valid shuffle of two distinct strings

May 23, 2023

What are Strings?

A string is a sequence of characters. In Java, strings are used to represent text. You can use strings to store messages, names, and other kinds of text data.
Strings are usually represented as a series of characters enclosed in quotation marks. For example, in Java, you can create a string like this:
String s = “Hello World”;

In this Article, we will write a program to check if a string is a valid shuffle of two distinct strings.

Strings:

We can use the various methods of the String class to manipulate strings.
For example, you can use the length() method to get the length of a string, the substring() method to get a substring of a string, and the toUpperCase() method to convert a string to uppercase. You can also use the + operator or the concat() method to concatenate two strings.

What is a Valid Shuffle?

A valid shuffle of two distinct strings is a new string that contains all the characters from both strings, but in a shuffled order. The shuffle must be such that it is not possible to tell which characters came from which original string.
For example, given the strings “abc” and “def”, some valid shuffles might include “dabcef”, “adbcef”, “abdecf”, etc. “abfedc” would not be a valid shuffle, because it is possible to tell which characters came from which original string.
There are many different ways to shuffle two strings, and the number of possible shuffles will depend on the lengths of the strings and the number of characters they contain. If the strings are of different lengths and contain no common characters, the number of possible shuffles will be the product of the lengths of the strings. If the strings have some characters in common, the number of possible shuffles will be less than this.

Program to Check if a string is a valid shuffle of two distinct strings :

Run

import java.util.Arrays;

public class Main {
    public static boolean isValidShuffle(String s, String t1, String t2) {
        if (t1.length() + t2.length() != s.length()) {
            return false;
        }
        char[] sChars = s.toCharArray();
        char[] t1Chars = t1.toCharArray();
        char[] t2Chars = t2.toCharArray();
        Arrays.sort(sChars);
        Arrays.sort(t1Chars);
        Arrays.sort(t2Chars);
        return Arrays.equals(sChars, mergeSortedArrays(t1Chars, t2Chars));
    }

    public static char[] mergeSortedArrays(char[] a, char[] b) {
        int aIndex = 0;
        int bIndex = 0;
        char[] merged = new char[a.length + b.length];
        for (int i = 0; i < merged.length; i++) {
            if (bIndex >= b.length || (aIndex < a.length && a[aIndex] <= b[bIndex])) {
                merged[i] = a[aIndex];
                aIndex++;
            } else {
                merged[i] = b[bIndex];
                bIndex++;
            }
        }
        return merged;
    }

    public static void main(String[] args) {
        String s = "abcdefgh";
        String t1 = "abcdefg";
        String t2 = "h";
        System.out.println(isValidShuffle(s, t1, t2));
    }
}

Output:

true

This code first checks if the lengths of the input string and the two other strings are compatible. If not, it returns False. Otherwise, it sorts the character arrays of the three strings and checks if the sorted array of the input string is equal to the sorted array obtained by merging the sorted arrays of the two other strings.

This solution has a time complexity of O(n log n), since it involves sorting the character arrays. It has a space complexity of O(n), since it creates three character arrays and a merged array.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others