String Character Matcher — Problem Statement & Solution Guide
Problem Description
You are given two strings, s1 and s2. Construct a new string that contains every character that appears in both s1 and s2. The characters in the result must appear in the same relative order as they do in s1, and each character may appear at most once, even if it occurs multiple times in either input string. The task is to produce this string efficiently for large inputs.
DSA Pattern Breakdown
DSA Pattern Breakdown
"String Character Matcher"
WHY DOES IT MATTER?
The set‑based filtering pattern is essential because many real‑world problems ask for elements common to two collections while preserving order; mastering it prevents costly nested loops and enables scalable solutions.
OPTIMIZATION CHALLENGE
The key insight is to pre‑process the smaller (or any) input into a constant‑time membership structure, then iterate the other input once, using a second structure to deduplicate output, collapsing a quadratic problem into linear time.
REAL-WORLD CONNECTION
Think of a distributed log aggregation system where you need to emit only the events that appear in both a master log and a filtered audit log, preserving the master’s chronological order—pre‑building a hash of audit IDs lets you stream the master log in a single pass.
In an interview, first ask about the character set size; if it’s bounded, immediately propose a fixed‑size bitmap. Otherwise, fall back to a hash set. This shows you consider both time and space constraints before coding.
COMPLEXITY AT A GLANCE
O(|s1| + |s2|)O(σ) where σ is the size of the character alphabet (or O(k) for k distinct characters in s2)Core Theory — Why This Approach?
The problem reduces to computing the intersection of two character multisets while preserving the order of the first string and eliminating duplicates. A naive double‑loop that checks every character of s1 against every character of s2 runs in O(|s1|·|s2|) time, which quickly becomes prohibitive for large inputs (e.g., strings of length 10^6). The optimal paradigm leverages constant‑time membership queries by materializing the character set of s2 in a hash‑based structure (or a fixed‑size boolean array for bounded alphabets). By scanning s1 once, we can decide in O(1) per character whether it belongs to the intersection and whether it has already been emitted, yielding a linear‑time solution. This approach exemplifies the “set‑based filtering” pattern, where pre‑processing one input into a lookup structure enables a single pass over the other input, dramatically reducing both time and auxiliary space compared to brute force.
Interview Questions on This Problem
Q1How would you modify the solution if the strings could contain Unicode characters beyond the basic ASCII range?
Use a hash set (e.g., std::unordered_set<char32_t> or a language’s built‑in Set) to store characters from s2, because the alphabet size is no longer bounded; the rest of the algorithm—single pass over s1 with a second set to track already‑output characters—remains unchanged, preserving O(n+m) time and O(k) space where k is the number of distinct Unicode code points present.
Q2Can you extend the algorithm to return the longest common subsequence (LCS) of distinct characters instead of just the intersection in order of s1?
The LCS problem is fundamentally different; it requires dynamic programming with O(|s1|·|s2|) time. However, if we restrict to distinct characters, we can map each character in s2 to its index, then transform s1 into a sequence of those indices (ignoring characters not in s2) and compute the longest increasing subsequence (LIS) on that sequence, achieving O(n log n) time.
Q3What are the trade‑offs between using a fixed‑size boolean array versus a hash set for the lookup structure?
A boolean array offers O(1) access with minimal constant factors and O(σ) space, where σ is the alphabet size (e.g., 256 for extended ASCII). It is ideal when the character set is small and known. A hash set handles arbitrary Unicode ranges with space proportional to the number of distinct characters actually present, but incurs higher constant overhead for hashing and possible collisions.
Examples
Input
{"s1":"abac","s2":"bca"}Output
abc
Explanation: The characters that appear in both strings are a, b, and c. In s1, the first occurrence of a is at position 0, b at 1, and c at 3. Thus the result preserves the order a → b → c, yielding "abc".
Input
{"s1":"xyz","s2":"abc"}Output
Explanation: There are no characters common to both strings, so the resulting string is empty.
Input
{"s1":"hello world","s2":"world"}Output
world
Explanation: The common characters are w, o, r, l, d. In s1, they appear in the order w (index 6), o (7), r (8), l (9), d (10). Removing duplicates and keeping this order gives "world".
Input
{"s1":"aaaa","s2":"aaab"}Output
a
Explanation: Only the character 'a' is shared by both strings. Even though it appears multiple times, it is included only once in the result.
Input
{"s1":"abcde","s2":"edcba"}Output
abcde
Explanation: All five characters are common. In s1 they appear in the order a, b, c, d, e, so the result is "abcde".
Constraints
- 1 <= len(s1), len(s2) <= 100000
- s1 and s2 consist of printable ASCII characters (code 32 to 126)
- The output string length will not exceed min(len(s1), len(s2))
- The algorithm should run in O(len(s1) + len(s2)) time and O(1) additional space (excluding the output).
Optimal Approach & Strategy
Build a hash set of characters from s2, then iterate s1 once, adding a character to the result only if it exists in the set and hasn’t been added before.
Brute Force Approach
Check each character of s1 against every character of s2 and keep a list of matches, then remove duplicates while preserving order.
Verified Code Solutions
function stringCharacterMatcher(s1, s2) {
const seen = new Set();
const result = [];
for (const char of s1) {
if (s2.includes(char) && !seen.has(char)) {
result.push(char);
seen.add(char);
}
}
return result;
}class Solution {
public: vector<string> stringCharacterMatcher(string s1, string s2) {
set<char> seen;
vector<char> result;
for (char c : s1) {
if (s2.find(c) != string::npos && seen.find(c) == seen.end()) {
result.push_back(c);
seen.insert(c);
}
}
return vector<string>(result.begin(), result.end());
}
}class Solution {
public String[] stringCharacterMatcher(String s1, String s2) {
Set<Character> seen = new HashSet<>();
List<Character> result = new ArrayList<>();
for (char c : s1.toCharArray()) {
if (s2.indexOf(c) != -1 && !seen.contains(c)) {
result.add(c);
seen.add(c);
}
}
return result.toArray(new String[0]);
}
}def string_character_matcher(s1, s2):
seen = set()
result = []
for char in s1:
if char in s2 and char not in seen:
result.append(char)
seen.add(char)
return resultfunction stringCharacterMatcher(s1, s2) {
const seen = new Set();
const result = [];
for (const char of s1) {
if (s2.includes(char) && !seen.has(char)) {
result.push(char);
seen.add(char);
}
}
return result;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.