Class StringInterleaving

java.lang.Object

topics.greedy.stringinterleaving.StringInterleaving

public class StringInterleaving
extends Object

String Interleaving

Checks if string C is formed by an interleaving of strings A and B. An interleaving maintains the relative order of characters from both original strings.

The Greedy Trap

This Greedy algorithm uses two pointers. It works perfectly when the characters of A and B are distinct or when there is no ambiguity. However, it fails if both A and B share the same current character, because the greedy choice (always picking A first) might lead to a dead end, missing a valid interleaving path.
(A guaranteed solution for all cases requires Dynamic Programming O(N*M)).

• Time Complexity: O(N) where N is the length of string C.
• Space Complexity: O(1) using pointers (no extra memory).

Author:

vicegd

Constructor Summary

Constructors

Constructor	Description
StringInterleaving()

Method Summary

Modifier and Type	Method	Description
boolean	isInterleaved(String a, String b, String c)	Attempts to verify interleaving using a purely greedy two-pointer strategy.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

StringInterleaving

public StringInterleaving()

Method Details

isInterleaved

public boolean isInterleaved(String a,
 String b,
 String c)

Attempts to verify interleaving using a purely greedy two-pointer strategy.

Parameters:

a - The first source string.

b - The second source string.

c - The target string to check.

Returns:

true if the greedy strategy successfully verifies the interleaving.