Loading…

easyBasicsSometimes asked

Check Substring

Basics · 6 min

Given two strings s and sub, return whether sub occurs somewhere inside s as a contiguous substring.

In plain English

Slide a window of length |sub| across s and compare; or use the built-in contains/indexOf.

Examples

Example 1

Input: s = "hello world", sub = "o w"
Output: true
Note: Found at index 4.

Example 2

Input: s = "abc", sub = "d"
Output: false
Note: Absent.

Example 3

Input: s = "abc", sub = ""
Output: true
Note: Empty is always a substring.

Constraints

0 ≤ s.length ≤ 10^4
0 ≤ sub.length ≤ s.length

Clarifying questions2First question: Can I use the library?Explore questions

Q1.Can I use the library?
I'd use contains in practice; I'll show the algorithm to demonstrate it.
Q2.Is an empty substring a match?
Yes, by convention it occurs at index 0.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Use `s.contains(sub)` / `sub in s`. To show the algorithm, check each start index `i` in `0..n-m` and compare the m characters. O(n·m) naive.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can write a correct windowed match and know its complexity / the KMP upgrade.

Where candidates slip

Start-range off-by-one, or mishandling the empty needle.

How to stand out

Describe KMP's failure function for O(n+m) matching.

Choose

Compare the available approaches

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

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 1 · Optimal

Sliding window compare

TimeO(n·m)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Try each start position where sub could still fit in s.

2Hint 2Explore hint

Compare |sub| characters at each start; what's the worst-case cost?

3Hint 3Explore hint

Remember the empty-needle case, and name the O(n+m) KMP upgrade.

A · Core idea

Decide whether sub occurs inside s. The library way is s.contains(sub); the algorithmic way is a sliding-window compare: at each start index in s, check whether the next |sub| characters match.

Why O(n·m) naive. There are up to n−m+1 start positions, and each comparison can take up to m characters, so the brute force is O(n·m). It's fine for fresher scope, but name the upgrade.

The empty-needle convention. An empty sub is a substring of every string (it 'occurs' at position 0), so return true for it. Mishandling this is a common edge-case slip.

The linear upgrade. KMP precomputes a failure function so it never re-compares characters, achieving O(n+m); indexOf/contains are typically optimised similarly. Mentioning KMP shows you know the brute force isn't optimal.

B · Visual dry run

Interactive dry run

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

s = "abcab", sub = "cab"

i=0

abc vs cab

Stateno

Final resulttrue

C · Code with teaching comments

solution.javaJava

Sliding window compare — optimal

2 teaching notes

1
public boolean contains(String s, String sub) {
2
    int n = s.length(), m = sub.length();
3
    for (int i = 0; i + m <= n; i++) {
4
        int j = 0;
5
        while (j < m && s.charAt(i + j) == sub.charAt(j)) j++;
6
        // All m characters matched — found it.
7
        if (j == m) return true;
8
    }
9
    return m == 0;
10
}

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

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

Mention KMP/indexOf as the O(n+m) upgrade over the O(n·m) scan.

ComplexityO(n·m) time, O(1) space — up to n−m+1 starts, each up to m comparisons → O(n·m); O(1) extra space.

E · Edge cases and pitfalls5s = "abc", sub = "" — Empty needle → true.Explore edge cases

Edge cases handled

s = "abc", sub = ""Empty needle → true.
s = "abc", sub = "d"Absent → false.
s = "abc", sub = "abc"Whole string matches → true.

Pitfalls

Off-by-one on the start range (i + m <= n).
Not returning true for an empty needle.

Practice

Try the solution yourself

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

Editable code previewpublic boolean contains(String s, String sub) { int n = s.length(), m = sub.length(); for (int i = 0; i + m <= n; i++) { int j = 0; while (j < m && s.charAt(i + j) == sub.charAt(j)) j++;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.

Off-by-one on the start range (i + m <= n).
Not returning true for an empty needle.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sliding window match

Code pattern to memorize

for i in 0..n-m: if s[i:i+m]==sub return true; (empty -> true)

Rules to remember

1Try each start 0..n-m.
2Compare m chars.
3Empty needle ⟹ true.

Use this pattern when

Substring search

Choose another pattern when

Very large inputs — use KMP/Z-algorithm for O(n+m)

Interview takeaway

Substring search is window matching; KMP makes it linear.

Continue

Transfer the pattern to another problem

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

Transferable patternA core fresher pattern: Sliding window match. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Implement strStr / indexOf
Coming soon
Return the index; KMP for O(n+m).

Same pattern

easyBasicsSometimes asked

Check Substring

Basics · 6 min

Given two strings s and sub, return whether sub occurs somewhere inside s as a contiguous substring.

In plain English

Slide a window of length |sub| across s and compare; or use the built-in contains/indexOf.

Examples

Example 1

Input: s = "hello world", sub = "o w"
Output: true
Note: Found at index 4.

Example 2

Input: s = "abc", sub = "d"
Output: false
Note: Absent.

Example 3

Input: s = "abc", sub = ""
Output: true
Note: Empty is always a substring.

Constraints

0 ≤ s.length ≤ 10^4
0 ≤ sub.length ≤ s.length

Clarifying questions2First question: Can I use the library?Explore questions

Q1.Can I use the library?
I'd use contains in practice; I'll show the algorithm to demonstrate it.
Q2.Is an empty substring a match?
Yes, by convention it occurs at index 0.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Use `s.contains(sub)` / `sub in s`. To show the algorithm, check each start index `i` in `0..n-m` and compare the m characters. O(n·m) naive.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can write a correct windowed match and know its complexity / the KMP upgrade.

Where candidates slip

Start-range off-by-one, or mishandling the empty needle.

How to stand out

Describe KMP's failure function for O(n+m) matching.

Choose

Compare the available approaches

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

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 1 · Optimal

Sliding window compare

TimeO(n·m)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Try each start position where sub could still fit in s.

2Hint 2Explore hint

Compare |sub| characters at each start; what's the worst-case cost?

3Hint 3Explore hint

Remember the empty-needle case, and name the O(n+m) KMP upgrade.

A · Core idea

Decide whether sub occurs inside s. The library way is s.contains(sub); the algorithmic way is a sliding-window compare: at each start index in s, check whether the next |sub| characters match.

Why O(n·m) naive. There are up to n−m+1 start positions, and each comparison can take up to m characters, so the brute force is O(n·m). It's fine for fresher scope, but name the upgrade.

The empty-needle convention. An empty sub is a substring of every string (it 'occurs' at position 0), so return true for it. Mishandling this is a common edge-case slip.

B · Visual dry run

Interactive dry run

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

s = "abcab", sub = "cab"

i=0

abc vs cab

Stateno

Final resulttrue

C · Code with teaching comments

solution.javaJava

Sliding window compare — optimal

2 teaching notes

1
public boolean contains(String s, String sub) {
2
    int n = s.length(), m = sub.length();
3
    for (int i = 0; i + m <= n; i++) {
4
        int j = 0;
5
        while (j < m && s.charAt(i + j) == sub.charAt(j)) j++;
6
        // All m characters matched — found it.
7
        if (j == m) return true;
8
    }
9
    return m == 0;
10
}

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

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

Mention KMP/indexOf as the O(n+m) upgrade over the O(n·m) scan.

ComplexityO(n·m) time, O(1) space — up to n−m+1 starts, each up to m comparisons → O(n·m); O(1) extra space.

E · Edge cases and pitfalls5s = "abc", sub = "" — Empty needle → true.Explore edge cases

Edge cases handled

s = "abc", sub = ""Empty needle → true.
s = "abc", sub = "d"Absent → false.
s = "abc", sub = "abc"Whole string matches → true.

Pitfalls

Off-by-one on the start range (i + m <= n).
Not returning true for an empty needle.

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.

Off-by-one on the start range (i + m <= n).
Not returning true for an empty needle.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sliding window match

Code pattern to memorize

for i in 0..n-m: if s[i:i+m]==sub return true; (empty -> true)

Rules to remember

1Try each start 0..n-m.
2Compare m chars.
3Empty needle ⟹ true.

Use this pattern when

Substring search

Choose another pattern when

Very large inputs — use KMP/Z-algorithm for O(n+m)

Interview takeaway

Substring search is window matching; KMP makes it linear.

Continue

Transfer the pattern to another problem

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

Transferable patternA core fresher pattern: Sliding window match. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Implement strStr / indexOf
Coming soon
Return the index; KMP for O(n+m).

Same pattern