StringProblem 6 of 43

Write a Program to check whether a string is a valid shuffle of two strings or not

Brute Force
Time: O(n)
Space: O(n)
Optimal
Time: O(n)
Space: O(1)

Problem Statement

Given three strings s1, s2, and result, check if result is a valid shuffle of s1 and s2. A valid shuffle means:

  1. result contains all characters from both s1 and s2
  2. The relative order of characters from s1 is maintained
  3. The relative order of characters from s2 is maintained

Example:

  • Input: s1 = "abc", s2 = "def", result = "adbcef"

  • Output: true

  • Explanation: Characters maintain their relative order: a-b-c and d-e-f

  • Input: s1 = "abc", s2 = "def", result = "abdecf"

  • Output: true

  • Input: s1 = "abc", s2 = "def", result = "abcfed"

  • Output: false (d-e-f order is violated: f comes before e and d)

Approach 1: Using Two Pointers (Optimal)

Intuition

Use two pointers to traverse s1 and s2. For each character in result, it must match either the current character in s1 or s2. If it matches, advance the corresponding pointer.

Algorithm

  1. Check if length of result equals len(s1) + len(s2)
  2. Use pointers i, j for s1 and s2 respectively
  3. For each character in result:
    • If it matches s1[i], increment i
    • Else if it matches s2[j], increment j
    • Else return false
  4. Return true if both pointers reached the end
java
public class Solution {
    public boolean isValidShuffle(String s1, String s2, String result) {
        int n1 = s1.length();
        int n2 = s2.length();
        
        // Length check
        if (result.length() != n1 + n2) {
            return false;
        }
        
        int i = 0, j = 0;
        
        for (char c : result.toCharArray()) {
            if (i < n1 && c == s1.charAt(i)) {
                i++;
            } else if (j < n2 && c == s2.charAt(j)) {
                j++;
            } else {
                return false;
            }
        }
        
        // Both strings should be fully traversed
        return i == n1 && j == n2;
    }
}

Complexity Analysis

  • Time Complexity: O(n) where n is length of result
  • Space Complexity: O(1) - Only using pointers

Approach 2: Handling Duplicate Characters with Recursion

Intuition

When both s1 and s2 have the same current character, we need to try both possibilities. This requires backtracking or recursion.

Algorithm

  1. If result is empty and both s1 and s2 are empty, return true
  2. If current char of result matches both s1 and s2, try both paths
  3. If matches only s1, continue with s1
  4. If matches only s2, continue with s2
  5. If no match, return false
java
import java.util.*;

public class Solution {
    public boolean isValidShuffle(String s1, String s2, String result) {
        if (result.length() != s1.length() + s2.length()) {
            return false;
        }
        return helper(s1, 0, s2, 0, result, 0);
    }
    
    private boolean helper(String s1, int i, String s2, int j, String result, int k) {
        if (k == result.length()) {
            return i == s1.length() && j == s2.length();
        }
        
        boolean match1 = i < s1.length() && s1.charAt(i) == result.charAt(k);
        boolean match2 = j < s2.length() && s2.charAt(j) == result.charAt(k);
        
        if (match1 && match2) {
            return helper(s1, i + 1, s2, j, result, k + 1) ||
                   helper(s1, i, s2, j + 1, result, k + 1);
        } else if (match1) {
            return helper(s1, i + 1, s2, j, result, k + 1);
        } else if (match2) {
            return helper(s1, i, s2, j + 1, result, k + 1);
        }
        
        return false;
    }
    
    // With memoization
    public boolean isValidShuffleMemo(String s1, String s2, String result) {
        if (result.length() != s1.length() + s2.length()) {
            return false;
        }
        Boolean[][] memo = new Boolean[s1.length() + 1][s2.length() + 1];
        return helperMemo(s1, 0, s2, 0, result, 0, memo);
    }
    
    private boolean helperMemo(String s1, int i, String s2, int j, 
                                String result, int k, Boolean[][] memo) {
        if (k == result.length()) {
            return i == s1.length() && j == s2.length();
        }
        
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        
        boolean match1 = i < s1.length() && s1.charAt(i) == result.charAt(k);
        boolean match2 = j < s2.length() && s2.charAt(j) == result.charAt(k);
        
        boolean res = false;
        if (match1 && match2) {
            res = helperMemo(s1, i + 1, s2, j, result, k + 1, memo) ||
                  helperMemo(s1, i, s2, j + 1, result, k + 1, memo);
        } else if (match1) {
            res = helperMemo(s1, i + 1, s2, j, result, k + 1, memo);
        } else if (match2) {
            res = helperMemo(s1, i, s2, j + 1, result, k + 1, memo);
        }
        
        memo[i][j] = res;
        return res;
    }
}

Complexity Analysis

  • Time Complexity: O(n*m) with memoization, O(2^n) without
  • Space Complexity: O(n*m) for memoization table

Approach 3: Frequency Count (Simple Validation Only)

Intuition

This only checks if result contains exactly the same characters as s1 + s2. It does NOT verify the order, so use this as a quick pre-check.

java
import java.util.*;

public class Solution {
    public boolean hasValidCharacters(String s1, String s2, String result) {
        if (result.length() != s1.length() + s2.length()) {
            return false;
        }
        
        Map<Character, Integer> freq = new HashMap<>();
        
        for (char c : s1.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        for (char c : s2.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        
        for (char c : result.toCharArray()) {
            int count = freq.getOrDefault(c, 0);
            if (count == 0) return false;
            freq.put(c, count - 1);
        }
        
        return true;
    }
}

Key Takeaways

  1. Two-pointer approach works perfectly when characters are unique
  2. Recursion with memoization is needed when dealing with duplicate characters
  3. The key constraint is maintaining relative order of characters from both strings
  4. Length check is an important early exit condition
  5. This problem is related to the "Interleaving String" problem (LeetCode 97)
  6. Frequency count alone cannot verify order - it's only a necessary condition, not sufficient
Previous
Write a Code to check whether one string is a rotation of another
Next
Count and Say problem