Substring Search - I Editorial

Practice Problem Link: Substring Search | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given two strings s1 and s2, find the first occurrence of s2 in s1 as a substring.

Approach

A simple solution is to traverse the string s1 and check every substring of s1 which has a length equal to string s2. As soon as substring s2 is found return the starting index at which it is found.

Analysis

• Time Complexity: O(n * m) where n and m are string lengths of s1 and s2 respectively.
• Auxiliary Space Complexity: O(1)

Implementation

C++

int findStartIndexOfSubstring(string s1, string s2) {
   if (s1.size() < s2.size()) {
       return - 1;
   }
   for (int i = 0; i <= s1.size() - s2.size(); i++) {
       int substringFound = 1;
       for (int j = 0; j < s2.size(); j++) {
           if (s1[i + j] != s2[j]) {
               substringFound = 0;
               break;
           }
       }
       if(substringFound == 1) {
           return i;
       }
   }
   return - 1;
}

Java

class Solution {
   int findStartIndexOfSubString(String s1, String s2) {
       if (s1.length() < s2.length()) {
           return - 1;
       }
       for (int i = 0; i <= s1.length() - s2.length(); i++) {
           int substringFound = 1;
           for (int j = 0; j < s2.length(); j++) {
               if (s1.charAt(i + j) != s2.charAt(j)) {
                   substringFound = 0;
                   break;
               }
           }
           if(substringFound == 1) {
               return i;
           }
       }
       return - 1;
   }
}