Loading…

easyStrings0Frequently asked

Two Strings

Q: How do you solve Two Strings using the Brute Force — Enumerate Every Substring approach?

When to use it: Mention it to show you can model the literal question, then immediately note it's wasteful because a single character already settles it. Translate the prompt word-for-word: for every substring of `s1`, ask whether it appears anywhere in `s2`. Two nested indices `i ≤ j` slice out `s1[i:j]`, and `s2.contains(...)` answers membership. **Why this is the literal-but-wrong-sized first attempt.** The question literally says 'common substring', so the mechanical response is to produce all substrings and test each one. It returns the correct answer — the first substring found in `s2` proves a shared substring exists. **Why it is enormously wasteful.** You're checking substrings of length 1, 2, 3, … but if *any* of them matches, a length-1 piece of it already matched. So all the work spent on longer substrings is redundant. The nested generation alone is O(n²), and each membership probe adds another O(m) factor — for `n = m = 10⁵` that's astronomically slow. **The realisation that shrinks it.** If `s1[i:j]` is a substring of `s2`, then its first character `s1[i]` is also a substring of `s2`. So you only ever needed to test single characters. That observation is the entire optimal algorithm — open with brute force, then collapse it. Time complexity: O(n² · m). Space complexity: O(n).

Q: How do you solve Two Strings using the Character-Set Intersection (Optimal) approach?

When to use it: The answer they want — phrase it as 'a single shared letter is a common substring, so I just intersect the character sets'. Record the alphabet of `s1` in a set, then walk `s2` and return `"YES"` at the first character that's already present. **Why this is correct and complete.** From the brute-force insight, a common substring of any length implies a common *character*. So the two strings share a substring exactly when their character sets intersect. Storing `s1`'s characters and probing each character of `s2` tests precisely that intersection. **Why it's O(1) space, not O(n).** The alphabet is fixed at 26 lowercase letters. A `boolean[26]` (or a Python set that can hold at most 26 distinct letters) never grows with input length, so the extra memory is constant. Say this explicitly — interviewers love the 'small fixed alphabet → O(1)' observation. **Why scan s2 lazily.** We return on the very first shared character. There's no benefit to building a second full set for `s2`; a single streaming pass with early exit is both simplest and fastest in the common case where a match appears early. **Build the set from the shorter string** if you want to shave constant-factor memory — correctness is unchanged, but the set is then bounded by the smaller alphabet. Time complexity: O(n + m). Space complexity: O(1).

Arrays & Hashing · 83 of 83 · 6 min

Given two strings, determine whether they share a common substring. A substring may be as small as a single character.

For each pair return the string "YES" if the two strings share any common substring, and "NO" if they do not.

In plain English

Because a substring can have length 1, 's1 and s2 share a common substring' is exactly equivalent to 's1 and s2 share at least one common letter'. If even one character appears in both, that character alone is a valid common substring. So we reduce the question to a membership test over a small alphabet.

Examples

Example 1

Input: s1 = "hello", s2 = "world"
Output: YES
Note: They share 'o' and 'l'. Either one alone is a common substring of length 1.

Example 2

Input: s1 = "hi", s2 = "world"
Output: NO
Note: {h, i} and {w, o, r, l, d} are disjoint — no shared character, so no common substring.

Example 3

Input: s1 = "a", s2 = "art"
Output: YES
Note: 'a' is in both — a single shared character is enough.

Constraints

1 ≤ |s1|, |s2| ≤ 10⁵
Both strings consist of lowercase English letters only
Return the literal strings "YES" or "NO"

Clarifying questions4First question: Does the common substring have to be longer than one character?Explore questions

Q1.Does the common substring have to be longer than one character?
No — a single shared character is itself a length-1 substring, which is what makes this an O(n) set-intersection problem rather than a DP.
Q2.What characters can appear?
Lowercase a–z only, so a fixed 26-element boolean array gives O(1) extra space.
Q3.Do I need to return the substring or just yes/no?
Just the strings "YES" or "NO". We only test existence, never reconstruct the match.
Q4.Could the strings be empty?
Constraints say length ≥ 1, but if one were empty the answer is trivially "NO" — no characters to share.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Two strings share a common substring if and only if they share at least one common character — because any single shared letter is itself a length-1 common substring. So you never need to enumerate substrings at all: build a set (or 26-slot boolean array) of the characters in one string and scan the other for any hit. Return "YES" on the first shared character, "NO" if none. O(n + m) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you notice that a length-1 substring counts, collapsing the problem to a set-intersection check, instead of mechanically generating every substring.

Where candidates slip

Enumerating all substrings of one string and searching for each inside the other — correct but O(n²·m), and a signal you missed the single-character insight.

How to stand out

Say out loud: 'A shared substring of length 1 is enough, so I just need to know if the two character sets intersect.' Then note the 26-letter alphabet gives O(1) space.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Enumerate Every Substring	`O(n² · m)`	`O(n)`	Mention it to show you can model the literal question, then immediately note it's wasteful because a single character already settles it.	Read
2	Character-Set Intersection (Optimal)Optimal	`O(n + m)`	`O(1)`	The answer they want — phrase it as 'a single shared letter is a common substring, so I just intersect the character sets'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewShare a common substring?Can a substring be length 1?YesNo (length >= k)Explore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Enumerate Every Substring

TimeO(n² · m)SpaceO(n)

Mention it to show you can model the literal question, then immediately note it's wasteful because a single character already settles it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The literal reading is 'is some substring of s1 also a substring of s2?'. What's the most direct way to test that?

2Hint 2Explore hint

Generate every substring of s1 with two nested indices (i, j), then check whether s2 contains it.

3Hint 3Explore hint

Each `contains` check is itself O(m), and there are O(n²) substrings — so this is O(n²·m). Correct, but a red flag that you've missed something simpler.

A · Core idea

Translate the prompt word-for-word: for every substring of s1, ask whether it appears anywhere in s2. Two nested indices i ≤ j slice out s1[i:j], and s2.contains(...) answers membership.

Why this is the literal-but-wrong-sized first attempt. The question literally says 'common substring', so the mechanical response is to produce all substrings and test each one. It returns the correct answer — the first substring found in s2 proves a shared substring exists.

Why it is enormously wasteful. You're checking substrings of length 1, 2, 3, … but if any of them matches, a length-1 piece of it already matched. So all the work spent on longer substrings is redundant. The nested generation alone is O(n²), and each membership probe adds another O(m) factor — for n = m = 10⁵ that's astronomically slow.

The realisation that shrinks it. If s1[i:j] is a substring of s2, then its first character s1[i] is also a substring of s2. So you only ever needed to test single characters. That observation is the entire optimal algorithm — open with brute force, then collapse it.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s1 = "abc", s2 = "cde"

Array state

i=0

test "a", "ab", "abc" — miss

i ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final resultYES

C · Code with teaching comments

Reference implementation previewpublic String twoStrings(String s1, String s2) { for (int i = 0; i < s1.length(); i++) { for (int j = i + 1; j <= s1.length(); j++) { String sub = s1.substring(i, j); if (s2.contains(sub)) {Explore the full code

solution.javaJava

Brute Force — Enumerate Every Substring — reference

3 teaching notes

1
public String twoStrings(String s1, String s2) {
2
    for (int i = 0; i < s1.length(); i++) {
3
        // j is exclusive end, so s1.substring(i, j) ranges from a single char up to the
4
        // whole tail.
5
        for (int j = i + 1; j <= s1.length(); j++) {
6
            String sub = s1.substring(i, j);
7
            // Each contains() is O(m); doing it for every substring is the O(n²·m)
8
            // cost.
9
            if (s2.contains(sub)) {
10
                // The first substring found in s2 proves existence — no need to keep
11
                // scanning.
12
                return "YES";
13
            }
14
        }
15
    }
16
    return "NO";
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n² · m) timeO(n) spaceOpen the invariant and proofExplore the proof

Every multi-character common substring contains a single common character. So the existence question for substrings of any length is equivalent to the existence question for length-1 substrings — which is just set intersection.

ComplexityO(n² · m) time, O(n) space — There are n(n+1)/2 ≈ n²/2 substrings of s1; testing each for membership in s2 with a naive `contains` is O(m). Total O(n²·m). Building substrings costs up to O(n) space each.

E · Edge cases and pitfalls3Generating all substrings when only single characters ever mattered.Explore edge cases

Pitfalls

Generating all substrings when only single characters ever mattered.
Off-by-one on the exclusive end index j (using j < length instead of j <= length skips the full-tail substring).
Calling contains() inside the inner loop and not realising it hides another O(m) factor.

03.2

Approach 2 of 2 · Optimal

Character-Set Intersection (Optimal)

TimeO(n + m)SpaceO(1)

The answer they want — phrase it as 'a single shared letter is a common substring, so I just intersect the character sets'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If any single character is shared, you're done. What data structure answers 'is this character present?' in O(1)?

2Hint 2Explore hint

Record every character of s1 in a set (or a boolean[26]). Then scan s2 once.

3Hint 3Explore hint

The moment a character of s2 is already in the set, return YES. If you finish the scan with no hit, return NO.

A · Core idea

Record the alphabet of s1 in a set, then walk s2 and return "YES" at the first character that's already present.

Why this is correct and complete. From the brute-force insight, a common substring of any length implies a common character. So the two strings share a substring exactly when their character sets intersect. Storing s1's characters and probing each character of s2 tests precisely that intersection.

Why it's O(1) space, not O(n). The alphabet is fixed at 26 lowercase letters. A boolean[26] (or a Python set that can hold at most 26 distinct letters) never grows with input length, so the extra memory is constant. Say this explicitly — interviewers love the 'small fixed alphabet → O(1)' observation.

Why scan s2 lazily. We return on the very first shared character. There's no benefit to building a second full set for s2; a single streaming pass with early exit is both simplest and fastest in the common case where a match appears early.

Build the set from the shorter string if you want to shave constant-factor memory — correctness is unchanged, but the set is then bounded by the smaller alphabet.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s1 = "hello", s2 = "world"

Hash-map state

build

ValueIndex / state

h→ ✓

e→ ✓

l→ ✓

o→ ✓

Continue scanning

insert h, e, l, o from "hello"

Final resultYES

C · Code with teaching comments

solution.javaJava

Character-Set Intersection (Optimal) — optimal

4 teaching notes

1
public String twoStrings(String s1, String s2) {
2
    // Fixed 26-slot array — O(1) space for a lowercase alphabet.
3
    boolean[] seen = new boolean[26];
4
    for (int i = 0; i < s1.length(); i++) {
5
        // Mark every character that appears in s1.
6
        seen[s1.charAt(i) - 'a'] = true;
7
    }
8
    for (int i = 0; i < s2.length(); i++) {
9
        // First character of s2 already seen → the two alphabets intersect.
10
        if (seen[s2.charAt(i) - 'a']) {
11
            // Early exit — one shared letter is a length-1 common substring.
12
            return "YES";
13
        }
14
    }
15
    return "NO";
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n + m) timeO(1) spaceOpen the invariant and proofExplore the proof

This is the canonical 'pay O(1) memory to buy O(1) membership tests' trade, identical in spirit to Two Sum's complement lookup. The cleverness isn't the data structure — it's realising the substring question was a length-1 question in disguise.

ComplexityO(n + m) time, O(1) space — Building the set is O(n). Scanning s2 is O(m). Each membership test is O(1). Total O(n + m). The set holds at most 26 distinct lowercase letters, so space is O(1).

E · Edge cases and pitfalls6s1 = "aaaa", s2 = "bbbb" — Set {a} vs characters {b} — disjoint → scan finishes with no hit → "NO".Explore edge cases

Edge cases handled

s1 = "aaaa", s2 = "bbbb"Set {a} vs characters {b} — disjoint → scan finishes with no hit → "NO".
s1 = "a", s2 = "art"Set {a}; first char of s2 is 'a' → immediate "YES".
s1 = "xy", s2 = "yx"Set {x, y}; 'y' is the first char of s2 and already present → "YES".

Pitfalls

Building a HashSet<Character> instead of a boolean[26] — works but is heavier than the O(1) array.
Returning a boolean true/false instead of the literal strings "YES"/"NO".
Computing the full intersection set when an early-exit scan is both simpler and faster.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic String twoStrings(String s1, String s2) { boolean[] seen = new boolean[26]; for (int i = 0; i < s1.length(); i++) { seen[s1.charAt(i) - 'a'] = true; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Enumerating substrings instead of characters

Any common substring contains a common character, so testing single characters is sufficient. The substring loop is O(n²·m) for no benefit.

Explore the code comparison

Don't write this

for i in range(len(s1)):
    for j in range(i + 1, len(s1) + 1):
        if s1[i:j] in s2:
            return "YES"

Write this instead

seen = set(s1)
for ch in s2:
    if ch in seen:
        return "YES"

Returning a boolean instead of YES/NO

The prompt's output contract is the literal strings. Returning True/False fails the grader even though the logic is right.

Explore the code comparison

Don't write this

return seen[s2.charAt(i) - 'a'];

Write this instead

if (seen[s2.charAt(i) - 'a']) return "YES";

Heavyweight set for a tiny alphabet

Only 26 lowercase letters are possible, so a boolean[26] is O(1) and cache-friendly; a HashSet adds boxing and hashing overhead.

Explore the code comparison

Don't write this

Set<Character> seen = new HashSet<>();

Write this instead

boolean[] seen = new boolean[26];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Character-set intersection (single shared letter suffices)

Code pattern to memorize

seen = set(s1)
for ch in s2:
    if ch in seen: return "YES"
return "NO"

Rules to remember

1A shared substring of length 1 is enough — so the whole problem collapses to 'do the two alphabets intersect?'.
2Build the set from the shorter string if you want to minimise memory; correctness is identical either way.
3Lowercase a–z means a 26-slot boolean array works → O(1) space, not O(n).
4Never enumerate substrings — that's the trap that turns an O(n) problem into O(n²·m).
5Return the string "YES" / "NO", not a boolean — match the prompt's output spec exactly.

Use this pattern when

Asked whether two strings share ANY common substring / character
You only need a yes/no answer, not the substring itself
Alphabet is small and fixed (a–z), so a boolean array is O(1)
You catch yourself about to write a nested substring loop — stop and think 'single char'

Choose another pattern when

Need the LONGEST common substring → that's dynamic programming, not set intersection
Need the actual shared substring text → you must track positions, not just membership
Substrings must be length ≥ k → can't shortcut to single characters
Order or contiguity of a longer match matters → suffix automaton / DP territory

Interview takeaway

The whole puzzle is a misdirection: it says 'substring' but a single shared letter already is one. Reducing 'common substring exists?' to 'character sets intersect?' is the insight that turns a brute-force enumeration into one linear pass.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternSet-membership / character-set intersection over a fixed alphabet. Whenever a string question only needs 'does any element appear in both?', collapse it to a set intersection in O(n + m). The trap here is wording: 'substring' sounds like DP, but a length-1 match makes it a single linear pass.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Longest Common Subsequence
Coming soon
Now order matters and you need the length — 2D DP, not a set check.
Maximum Length of Repeated Subarray (Longest Common Substring)
Coming soon
Longest CONTIGUOUS common run — DP on dp[i][j] = match length ending here.
Intersection of Two Arrays
Coming soon
Same set-intersection idea, but return the shared elements instead of yes/no.
Valid Anagram
Also reduces to character frequency over a fixed alphabet.

Same pattern

←

Sherlock and the Valid String

easyStrings0Frequently asked

Two Strings

Arrays & Hashing · 83 of 83 · 6 min

Given two strings, determine whether they share a common substring. A substring may be as small as a single character.

For each pair return the string "YES" if the two strings share any common substring, and "NO" if they do not.

In plain English

Examples

Example 1

Input: s1 = "hello", s2 = "world"
Output: YES
Note: They share 'o' and 'l'. Either one alone is a common substring of length 1.

Example 2

Input: s1 = "hi", s2 = "world"
Output: NO
Note: {h, i} and {w, o, r, l, d} are disjoint — no shared character, so no common substring.

Example 3

Input: s1 = "a", s2 = "art"
Output: YES
Note: 'a' is in both — a single shared character is enough.

Constraints

1 ≤ |s1|, |s2| ≤ 10⁵
Both strings consist of lowercase English letters only
Return the literal strings "YES" or "NO"

Clarifying questions4First question: Does the common substring have to be longer than one character?Explore questions

Q1.Does the common substring have to be longer than one character?
No — a single shared character is itself a length-1 substring, which is what makes this an O(n) set-intersection problem rather than a DP.
Q2.What characters can appear?
Lowercase a–z only, so a fixed 26-element boolean array gives O(1) extra space.
Q3.Do I need to return the substring or just yes/no?
Just the strings "YES" or "NO". We only test existence, never reconstruct the match.
Q4.Could the strings be empty?
Constraints say length ≥ 1, but if one were empty the answer is trivially "NO" — no characters to share.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you notice that a length-1 substring counts, collapsing the problem to a set-intersection check, instead of mechanically generating every substring.

Where candidates slip

Enumerating all substrings of one string and searching for each inside the other — correct but O(n²·m), and a signal you missed the single-character insight.

How to stand out

Say out loud: 'A shared substring of length 1 is enough, so I just need to know if the two character sets intersect.' Then note the 26-letter alphabet gives O(1) space.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Enumerate Every Substring	`O(n² · m)`	`O(n)`	Mention it to show you can model the literal question, then immediately note it's wasteful because a single character already settles it.	Read
2	Character-Set Intersection (Optimal)Optimal	`O(n + m)`	`O(1)`	The answer they want — phrase it as 'a single shared letter is a common substring, so I just intersect the character sets'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Enumerate Every Substring

TimeO(n² · m)SpaceO(n)

Mention it to show you can model the literal question, then immediately note it's wasteful because a single character already settles it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The literal reading is 'is some substring of s1 also a substring of s2?'. What's the most direct way to test that?

2Hint 2Explore hint

Generate every substring of s1 with two nested indices (i, j), then check whether s2 contains it.

3Hint 3Explore hint

Each `contains` check is itself O(m), and there are O(n²) substrings — so this is O(n²·m). Correct, but a red flag that you've missed something simpler.

A · Core idea

Translate the prompt word-for-word: for every substring of s1, ask whether it appears anywhere in s2. Two nested indices i ≤ j slice out s1[i:j], and s2.contains(...) answers membership.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s1 = "abc", s2 = "cde"

Array state

i=0

test "a", "ab", "abc" — miss

i ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final resultYES

C · Code with teaching comments

solution.javaJava

Brute Force — Enumerate Every Substring — reference

3 teaching notes

1
public String twoStrings(String s1, String s2) {
2
    for (int i = 0; i < s1.length(); i++) {
3
        // j is exclusive end, so s1.substring(i, j) ranges from a single char up to the
4
        // whole tail.
5
        for (int j = i + 1; j <= s1.length(); j++) {
6
            String sub = s1.substring(i, j);
7
            // Each contains() is O(m); doing it for every substring is the O(n²·m)
8
            // cost.
9
            if (s2.contains(sub)) {
10
                // The first substring found in s2 proves existence — no need to keep
11
                // scanning.
12
                return "YES";
13
            }
14
        }
15
    }
16
    return "NO";
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n² · m) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Generating all substrings when only single characters ever mattered.Explore edge cases

Pitfalls

Generating all substrings when only single characters ever mattered.
Off-by-one on the exclusive end index j (using j < length instead of j <= length skips the full-tail substring).
Calling contains() inside the inner loop and not realising it hides another O(m) factor.

03.2

Approach 2 of 2 · Optimal

Character-Set Intersection (Optimal)

TimeO(n + m)SpaceO(1)

The answer they want — phrase it as 'a single shared letter is a common substring, so I just intersect the character sets'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If any single character is shared, you're done. What data structure answers 'is this character present?' in O(1)?

2Hint 2Explore hint

Record every character of s1 in a set (or a boolean[26]). Then scan s2 once.

3Hint 3Explore hint

The moment a character of s2 is already in the set, return YES. If you finish the scan with no hit, return NO.

A · Core idea

Record the alphabet of s1 in a set, then walk s2 and return "YES" at the first character that's already present.

Build the set from the shorter string if you want to shave constant-factor memory — correctness is unchanged, but the set is then bounded by the smaller alphabet.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s1 = "hello", s2 = "world"

Hash-map state

build

ValueIndex / state

h→ ✓

e→ ✓

l→ ✓

o→ ✓

Continue scanning

insert h, e, l, o from "hello"

Final resultYES

C · Code with teaching comments

solution.javaJava

Character-Set Intersection (Optimal) — optimal

4 teaching notes

1
public String twoStrings(String s1, String s2) {
2
    // Fixed 26-slot array — O(1) space for a lowercase alphabet.
3
    boolean[] seen = new boolean[26];
4
    for (int i = 0; i < s1.length(); i++) {
5
        // Mark every character that appears in s1.
6
        seen[s1.charAt(i) - 'a'] = true;
7
    }
8
    for (int i = 0; i < s2.length(); i++) {
9
        // First character of s2 already seen → the two alphabets intersect.
10
        if (seen[s2.charAt(i) - 'a']) {
11
            // Early exit — one shared letter is a length-1 common substring.
12
            return "YES";
13
        }
14
    }
15
    return "NO";
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n + m) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6s1 = "aaaa", s2 = "bbbb" — Set {a} vs characters {b} — disjoint → scan finishes with no hit → "NO".Explore edge cases

Edge cases handled

s1 = "aaaa", s2 = "bbbb"Set {a} vs characters {b} — disjoint → scan finishes with no hit → "NO".
s1 = "a", s2 = "art"Set {a}; first char of s2 is 'a' → immediate "YES".
s1 = "xy", s2 = "yx"Set {x, y}; 'y' is the first char of s2 and already present → "YES".

Pitfalls

Building a HashSet<Character> instead of a boolean[26] — works but is heavier than the O(1) array.
Returning a boolean true/false instead of the literal strings "YES"/"NO".
Computing the full intersection set when an early-exit scan is both simpler and faster.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Enumerating substrings instead of characters

Any common substring contains a common character, so testing single characters is sufficient. The substring loop is O(n²·m) for no benefit.

Explore the code comparison

Don't write this

for i in range(len(s1)):
    for j in range(i + 1, len(s1) + 1):
        if s1[i:j] in s2:
            return "YES"

Write this instead

seen = set(s1)
for ch in s2:
    if ch in seen:
        return "YES"

Returning a boolean instead of YES/NO

The prompt's output contract is the literal strings. Returning True/False fails the grader even though the logic is right.

Explore the code comparison

Don't write this

return seen[s2.charAt(i) - 'a'];

Write this instead

if (seen[s2.charAt(i) - 'a']) return "YES";

Heavyweight set for a tiny alphabet

Only 26 lowercase letters are possible, so a boolean[26] is O(1) and cache-friendly; a HashSet adds boxing and hashing overhead.

Explore the code comparison

Don't write this

Set<Character> seen = new HashSet<>();

Write this instead

boolean[] seen = new boolean[26];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Character-set intersection (single shared letter suffices)

Code pattern to memorize

seen = set(s1)
for ch in s2:
    if ch in seen: return "YES"
return "NO"

Rules to remember

1A shared substring of length 1 is enough — so the whole problem collapses to 'do the two alphabets intersect?'.
2Build the set from the shorter string if you want to minimise memory; correctness is identical either way.
3Lowercase a–z means a 26-slot boolean array works → O(1) space, not O(n).
4Never enumerate substrings — that's the trap that turns an O(n) problem into O(n²·m).
5Return the string "YES" / "NO", not a boolean — match the prompt's output spec exactly.

Use this pattern when

Asked whether two strings share ANY common substring / character
You only need a yes/no answer, not the substring itself
Alphabet is small and fixed (a–z), so a boolean array is O(1)
You catch yourself about to write a nested substring loop — stop and think 'single char'

Choose another pattern when

Need the LONGEST common substring → that's dynamic programming, not set intersection
Need the actual shared substring text → you must track positions, not just membership
Substrings must be length ≥ k → can't shortcut to single characters
Order or contiguity of a longer match matters → suffix automaton / DP territory

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Longest Common Subsequence
Coming soon
Now order matters and you need the length — 2D DP, not a set check.
Maximum Length of Repeated Subarray (Longest Common Substring)
Coming soon
Longest CONTIGUOUS common run — DP on dp[i][j] = match length ending here.
Intersection of Two Arrays
Coming soon
Same set-intersection idea, but return the shared elements instead of yes/no.
Valid Anagram
Also reduces to character frequency over a fixed alphabet.

Same pattern

←

Sherlock and the Valid String