top of page

### Looking to master object-oriented and system design for tech interviews or career growth?

• Improve your system design and machine coding skills.

• Study with our helpful resources.

**We're in beta mode and would love to hear your feedback.

Search

# Implement StrStr Interviewbit Solution

Problem Statement:

Implement strStr(). strstr - locate a substring ( needle ) in a string ( haystack ). Try not to use standard library string functions for this question. Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

NOTE: Good clarification questions:

1. What should be the return value if the needle is empty?

2. What if both haystack and needle are empty?

For the purpose of this problem, assume that the return value should be -1 in both cases.

## Approach

Approach is to use a sliding window concept. Take a prefix of string B of size equal to the size of string A. And then keep moving forward and append the new character at the end, and remove the first character from the start. For each iteration keep comparing our current string with string A. If there is a match return the index from which the our current string has started.

## Time & Space Complexity

```Time Complexity: O(N*M)
Space Complexity: O(M)```

Where, N and M is the size of string B & A respectively.

Code in C++

bottom of page