Naga Vara Pradeep, Yendluri

Home | LinkedIn | GitHub

Find The Index Of The First Occurrence In A String

Given 2 strings - haystack and needle.

Problem statement

Find the index of needle substring if present in haystack and return starting index of the first occurrence, else return -1.

Intuition Use Window Sliding technique

Idea is to iterate from 0 till length of haystack - length of needle, this will help us not to overrun the last index.


function find_occurence{ loop i: 0 to haystack.length-needle.length{ haystack.substring(i, i+needle.length) == needle return index } return -1 }


haystack: hadel, needle: ade

In first iteration,

haystack substring from 0, 0+3 is had.

checking had equal to ade

not equal going to next iteration.

In second iteration, haystack substring from 1, 1+3 is ade checking ade equals to ade true, return index i i.e., 1

Java Implementation

class Solution {
    public int strStr(String haystack, String needle) {
        // taking lengths of both the given strings
        int ln = needle.length();
        int lh = haystack.length();
        for (int i = 0; i <= lh - ln; i++) { 
            // checking if substring of haystack of size needle string from 
            // current index to the needle string.
            if (haystack.substring(i, i + ln).equals(needle)) { 
                // we found needle string in haystack, we'll
                return index i 
                // to save time and computation, since we only need index of 
                // first occurence. 
                return i; 
        // Finally we return -1 since we haven't found needle in haystack
        return -1;