Community

Start a Thread
Filters
By Category
Notifications
Subscribe You’re not receiving notifications from this thread.

Detect Substring In String (Main Thread)

Here is the interview question prompt, presented for reference.

How would you write a function to detect a substring in a string?

If the substring can be found in the string, return the index at which it starts. Otherwise, return -1.

function detectSubstring(str, subStr) {
  return -1;
}

Important-- do not use the native String class's built-in substring or substr method. This exercise is to understand the underlying implementation of that method.

Constraints

  • Length of both the given strings <=100000
  • The strings would never be null
  • The strings will only consist of lowercase letters
  • Expected time complexity : O(n)
  • Expected space complexity : O(1)

You can see the full challenge with visuals at this link.

Challenges • Asked about 4 years ago by Tonya Sims

Jake from AlgoDaily Commented on Feb 27, 2020:

This is the main discussion thread generated for Detect Substring In String.

Tonya Sims Commented on Feb 27, 2020:

Hi! I'm using Python and trying not to peek at the answer, but is using the find() method an efficient solution? Or should we something where we're keeping track of the indexes with pointers?

Seth Commented on Jul 16, 2021:

What is the point of keeping the variable idxOfStart if it is never used in the final solution?

Kevin C Menezes Commented on Nov 30, 2021:

Echoing Seth's comment, what's the use of the "idxOfStart" variable?

Kiran sanubala Commented on Jan 21, 2022:

a='a cat in the hat'
b='hat'
start=0
end=int(len(a))
leap=int(len(b))
while start<=end:
if a[start:leap]==b:
print(start)
else:
start=start+1
leap=leap+1

I am using this code to find the substring in a string. It is working but going into an infinite loop. Can someone help me with what i am doing wrong?

Jake from AlgoDaily Commented on Jan 23, 2022:

Hey Kiran,

I formatted your code so it's easier to read:

py
a='a cat in the hat'
b='hat'
start=0
end=int(len(a))
leap=int(len(b))

while start<=end:
  if a[start:leap]==b:
  print(start)
else:
  start=start+1
  leap=leap+1

The problem seems to be the else statement. Instead of adding 1 to both the start and leap, you want to add 1 to the start and subtract 1 from the end. That way you're moving the pointers closer together, getting closer to the start <= end clause.

Fatih Commented on Feb 18, 2022:

Question's test cases better to cover one more edge case..
python
def test_4(self):
assert detectSubstring("aaaaab", "aab") == 3
print(
"PASSED: `detectSubstring('aaaaab', 'aab')` should return `3`"
)

Fatih Commented on Feb 18, 2022:

And some part of illustrative description is wrong.
3 X 6 = 12 how come? it should be 3 x 4 = 12