Quick Overview

Implement direct substring containment by checking each possible starting position. Handle empty patterns and boundary cases, and explain the repeated-prefix inputs that produce quadratic work.

Check Whether One String Contains Another by Direct Comparison

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a text string and a pattern string, determine whether the pattern occurs as a contiguous substring of the text. Use a direct brute-force comparison algorithm. ### Constraints and Clarifications For this practice interface, return a Boolean, use exact case-sensitive character equality, and define the empty pattern as present in every text. The report specifies containment and brute force but no encoding or numerical bounds; treat strings as sequences of comparable characters without normalization. ### What a Strong Answer Covers Try each valid start position, stop comparing a start at its first mismatch, and handle empty or longer patterns. Explain worst-case time and constant auxiliary space. ### Follow-up Questions - What pattern of repeated characters makes this approach slow? - What additional preprocessing could avoid repeated comparisons?

Overview: Implement direct substring containment by checking each possible starting position. Handle empty patterns and boundary cases, and explain the repeated-prefix inputs that produce quadratic work.

Given a text string and a pattern string, determine whether the pattern occurs as a contiguous substring of the text. Use a direct brute-force comparison algorithm. Implement containsPattern(text, pattern) and return a Boolean. Compare characters exactly and case-sensitively, without normalization. The empty pattern is present in every text, including the empty text.

Constraints

  • text and pattern are strings of characters; the source gives no length bound or encoding restriction.
  • A match must use consecutive characters in the same order.
  • Comparison is case-sensitive and does not normalize characters.
  • The empty pattern returns true for every text.

Examples

Input: ('', '')

Expected Output: True

Explanation: The empty pattern occurs in the empty text.

Input: ('', 'a')

Expected Output: False

Explanation: A nonempty pattern cannot fit in empty text.

Hints

  1. Consider what the empty pattern means before checking possible positions.
  2. A longer pattern cannot fit into a shorter text.

Loading coding console...

Show the approach

Approach

An empty pattern succeeds immediately, while a pattern longer than the text cannot fit. For each possible start, compare consecutive characters until a mismatch or the whole pattern matches. A complete comparison proves containment; if every start fails, no contiguous occurrence exists. Python compares its string characters directly. JavaScript and Java advance string indices by each Unicode code point width without creating arrays. For valid UTF-8, the C++ byte comparison has the same substring result: a valid encoded pattern begins with an ASCII or leading byte, so it cannot match from a continuation byte. The C++ signature uses const references to avoid copying input strings. Thus each reference uses constant auxiliary space and case-sensitive direct comparison without normalization.

Time complexity:
O(n * m) worst case for text length n and pattern length m
Space complexity:
O(1) auxiliary space