Very Common FAANG Interview Question! | Index of the First Occurrence in a String - Leetcode 28

dynamic programming, leetcode, coding interview question, data structures, data structures and algorithms, faang

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[davidespinosa]

(1) This is the brute force solution. Anyone who finds this hard should take an intro to programing class.
(2) Ask the interviewer whether they want to see the brute force solution -- sometimes they do, sometimes they don't.
(3) A rolling hash is a good non-brute force solution.

[geansantos]

much simpler:

haystack ='cabackssad'
needle = 'sad'

for i in range(len(haystack)):
if haystack[i:len(needle)+i] == needle:
print(i)

[manishts]

Kmp algorithm would be better alternative compared to naive, it has a better time complexity

[Crazmuss]

My python code solution would be
from dumb_interview_questions import haystack_and_needle
print(haystack_and_needle.find(haystack, needle)

[_TeXoN_]

Ok here is what I would do:
1. Inverse needle string
2. Pad inverse needle string with zeros, so the lengths are equal.
3. Fourier transform both the haystack and the inverse needle
4. Multiply the transdormations element by element.
5. Inverse fourier transform the result
6. Find maximum and return index
This should run in O(n log(n)) and also indicate near misses and find needles with dublicate letters.

[hueydo]

Nah use sliding window is more intuitive. Get the fixed size window in needle. Now do for loop from 0 to haystack length - needle length + 1. Then just do check string

[LearnEarnTrascend]

This is called the Brute force algorithm in string searching.

[pranjuljain]

I was thinking of solving it with dp, the logic will be quite similar to longest substring question

[nickbarton]

Firstly, iterate i from 0 to haystack length minus the needle length -1, no need to boundary check. Also, you don't need k because it equals i + j so just iterate j from 1 to length -1 of the needle, already checked the first character.

[RhymesWithCarbon]

I used an exception:
index_of: int
try:
index_of = haystack.index(needle)
except:
index_of = -1
return index_of

[ottik]

When everybody here shots hc solutions, i will add one myself...

1) tranform needle to into state automat, which has first state pointing to itself in every character.

2) make automat determinstic using state automat determinization algorithm

3) throw haystack into automat, w8 for final state. When it finishes, subtract length of needle from automat final position in hs, and you got result

4) profit

[llumnate]

This problem has multiple linear solutions, starting from prefix functions ending with suffix trees

[SirBearingtonSupporter]

string.indexOf(string, ?integer)
$parameter string - the substring to locate (needle)
$parameter ?integer - optional starting index to begin searching.

Languages with this as a built in:
C, C++, C#, Java, Python, JavaScript, Lua, SQL, COBOL, …

[evancono]

This one is for complete beginners. FYI you can solve it with just one for loop even if you don't use splicing

[BHARATHS-vm]

def strStr(self, haystack: str, needle: str) -> int:
if haystack == needle :
return 0
for i in
if
return I
return -1

[Speiger]

If you have a partial match instead of retesting all these characters you can simply offset the i curser and jump the partial match to the character that didnt match.

Since you jump to the missmatch you can retry the logic there and not skip a potential solution.

For longer words this is huge optimization. Since only test 1 character twice if a partial match happens.

[rdubb]

It’s an LC easy but an important fundamental one. Brute force is fine since it’s an LC easy. Probably a screening question for Fang, then next rounds they hit you with the LC mediums

[Awesomo]

Can be optimized a bit especially in cases with a lot of partial matches.
The simplest case is where the first character of the needle is only once in the needle. When the "b" didn't match the "d", you shouldn't have incremented i by one, but set i to the current value of k. As you already implicitly checked that the first needle character is only once in the haystack from i to k-1.

[nitendrakumar]

you should use kmp algo for pattern searching in a string