Definition
2D DP where dp[i][j] is true if the first i characters of s1 and first j of s2 can interleave to form the first i+j characters of s3. dp[i][j] holds if the last char came from s1 (dp[i−1][j] and s1[i−1]==s3[i+j−1]) or from s2 (dp[i][j−1] and s2[j−1]==s3[i+j−1]). Time O(m·n), space O(n).
A merge auditor at National Bank of India checks whether a combined transaction stream was produced by interleaving two source streams without reordering either. At each merged position she asks whether the next character could have come from stream one or from stream two, keeping each stream's internal order.
Understanding the Concepts
What is the problem?
Interleaving String — can two strings interleave to form a third. Given strings s1, s2, and s3, determine whether s3 is formed by interleaving s1 and s2, preserving the left-to-right order of each.
How does the approach work?
First, if the length of s3 is not the sum of the lengths of s1 and s2, return false immediately. Otherwise build a boolean table dp of size (m+1) by (n+1), where dp[i][j] says whether the first i of s1 and first j of s2 can interleave into the first i+j of s3. The base case dp[0][0] is true.
Each merged character at position i+j−1 of s3 must come from either s1 or s2. It came from s1 if dp[i−1][j] is true and s1 at i−1 equals s3 at i+j−1; it came from s2 if dp[i][j−1] is true and s2 at j−1 equals s3 at i+j−1. For example: dp[i][j] = (i>0 && dp[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1)) || (j>0 && dp[i][j-1] && s2.charAt(j-1)==s3.charAt(i+j-1));. The answer is dp[m][n].
The time is O(m·n) and space reduces to O(n) with a rolling row. A senior nuance is that a naive recursive interleaving check branches exponentially, so the whole point of the DP is to collapse the overlapping subproblems defined purely by the pair of prefix lengths.
What is the banking use case?
The mini-project builds a StreamMergeAuditor, a BankLogFormatter, and a runnable demo.
How do you implement this in Java?
// ─── File: src/main/java/com/bank/merge/StreamMergeAuditor.java ───
package com.bank.merge;
import java.util.logging.Logger;
public class StreamMergeAuditor {
private static final Logger log = Logger.getLogger(StreamMergeAuditor.class.getName());
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length();
if (m + n != s3.length()) { // length must match exactly
log.warning("Length mismatch; not an interleaving");
return false;
}
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true; // empty + empty = empty
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i > 0 && dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) {
dp[i][j] = true; // last char came from s1
}
if (j > 0 && dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)) {
dp[i][j] = true; // last char came from s2
}
}
}
boolean result = dp[m][n];
log.info(() -> "isInterleave = " + result);
return result;
}
}
// ─── File: src/main/java/com/bank/merge/BankLogFormatter.java ───
package com.bank.merge;
import java.util.logging.Formatter;
import java.util.logging.LogRecord;
import java.time.Instant;
public class BankLogFormatter extends Formatter {
@Override
public String format(LogRecord record) {
return String.format("%s [%s] %s%n",
Instant.ofEpochMilli(record.getMillis()),
record.getLevel(),
record.getMessage());
}
}
// ─── File: src/main/java/com/bank/merge/InterleavingDemo.java ───
package com.bank.merge;
import java.util.logging.ConsoleHandler;
import java.util.logging.Logger;
public class InterleavingDemo {
private static final Logger log = Logger.getLogger(InterleavingDemo.class.getName());
static {
Logger root = Logger.getLogger("");
for (var h : root.getHandlers()) root.removeHandler(h);
ConsoleHandler handler = new ConsoleHandler();
handler.setFormatter(new BankLogFormatter());
root.addHandler(handler);
}
public static void main(String[] args) {
log.info("National Bank of India — Stream Merge Auditor (Interleaving String)");
StreamMergeAuditor auditor = new StreamMergeAuditor();
log.info("aabcc + dbbca = aadbbcbcac → " +
auditor.isInterleave("aabcc", "dbbca", "aadbbcbcac")); // true
log.info("aabcc + dbbca = aadbbbaccc → " +
auditor.isInterleave("aabcc", "dbbca", "aadbbbaccc")); // false
}
}
What is the project structure?
stream-merge-service/
├── pom.xml
├── src/main/java/com/bank/merge/
│ ├── InterleavingDemo.java (main runnable demo)
│ ├── StreamMergeAuditor.java (2D interleave DP)
│ └── BankLogFormatter.java
└── src/test/java/com/bank/merge/
└── StreamMergeAuditorTest.java
How do you build and run?
# Compile
javac -d target/classes src/main/java/com/bank/merge/*.java
# Run
java -cp target/classes com.bank.merge.InterleavingDemo
What is the step-by-step walkthrough?
The inputs are aabcc, dbbca, and the candidate aadbbcbcac.
2026-10-27T04:10:00Z [INFO] National Bank of India — Stream Merge Auditor (Interleaving String) 2026-10-27T04:10:00Z [INFO] isInterleave = true 2026-10-27T04:10:00Z [INFO] aabcc + dbbca = aadbbcbcac → true 2026-10-27T04:10:00Z [INFO] isInterleave = false 2026-10-27T04:10:00Z [INFO] aabcc + dbbca = aadbbbaccc → false
What is the high-level design?
═══ HLD — Stream Merge Auditor ═══
┌────────────┐ 2 feeds+merged ┌──────────────┐ ┌──────────────────┐
│ Audit UI │───────────────→│ Merge Svc │→│ bool dp[i][j] │
└────────────┘ │ (Spring ×N) │ └──────────────────┘
└──────┬───────┘
│ valid interleave? → certify
▼
Reconciliation Report
What is the low-level design?
═══ LLD — Interleaving String ═══ ┌─ Technique ──────────────────────────────────────────────┐ │ dp[i][j]=(fromS1 & match) || (fromS2 & match) │ │ len(s3)==m+n guard; O(m·n); rolling row O(n) │ └──────────────────────────────────────────────────────────┘ ┌───────────────────────────────────────┐ │ StreamMergeAuditor │ │ + isInterleave(s1,s2,s3): boolean │ O(m·n) └───────────────────────────────────────┘
What is the time and space complexity?
Analyze the solution based on the algorithm used. Consider both the time to process input and the space required for any data structures.
What are common mistakes?
Common mistakes include off-by-one errors, not handling edge cases like empty input, and not considering the constraints of the problem.
What are the edge cases?
Edge cases include empty input, single element input, all identical elements, and boundary values.
What should a senior engineer know?
A senior engineer should understand the time-space tradeoffs, be able to explain the algorithm clearly, and know when this technique applies versus alternatives.
Visual Overview
s1=aabcc s2=dbbca s3=aadbbcbcac (len 5+5=10)
dp[0][0]=true
dp[i][j] = (dp[i-1][j] && s1[i-1]==s3[i+j-1]) ← char from s1
|| (dp[i][j-1] && s2[j-1]==s3[i+j-1]) ← char from s2
dp[5][5] = true → valid interleaving
Key Takeaway
Interleaving String is a two-dimensional dynamic programming problem. First I do a quick guard: if the length of the third string is not the sum of the lengths of the first two, it cannot be an interleaving, so I return false immediately. Otherwise I define dp of i and j as whether the first i characters of the first string and the first j of the second can interleave to form the first i plus j characters of the third.
For each cell the current merged character must have come from exactly one of the two sources. It came from the first string if the cell above was reachable and the first string's character matches, or it came from the second string if the cell to the left was reachable and the second string's character matches. The base case is the empty-empty cell being true, and the answer is the bottom-right cell.
In my project at National Bank of India, a merge auditor verified that a combined event stream was produced by interleaving two source feeds without reordering either. A greedy match fails when both feeds offer the same next character and only one choice completes a valid interleave, so I used this DP keyed on the pair of prefix lengths, which collapses the exponential recursion into a quadratic table.
Remember one sentence: understand the core algorithm and apply it to banking domain problems.
---