Find the Index of the First Occurrence in a String

Find the Index of the First Occurrence in a String is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the String Manipulation Patterns pattern, in the Naive / KMP / Rabin-Karp subpattern.

Problem statement

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "sadbutsad", needle = "sad" Output: 0 Explanation: "sad" occurs at index 0 and 6. The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto" Output: -1 Explanation: "leeto" did not occur in "leetcode", so we return -1.

Constraints:

- 1 <= haystack.length, needle.length <= 104

- haystack and needle consist of only lowercase English characters.

Topics and companies

Topics: Two Pointers, String, String Matching.

How to practise Find the Index of the First Occurrence in a String on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n + m), where n = haystack.length() and m = needle.length(). Building the prefix table (lps) takes O(m), and the search phase takes O(n). time and O(m), for the prefix table (lps) of the needle. space.

Open Find the Index of the First Occurrence in a String in the code editor, or read the Find the Index of the First Occurrence in a String editorial for a worked solution with its approach and complexity analysis.

Where Find the Index of the First Occurrence in a String sits in the DSA pattern sheet

• String Manipulation Patterns pattern guide
• Naive / KMP / Rabin-Karp subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Find the Index of the First Occurrence in a String

Other problems that use the same Naive / KMP / Rabin-Karp and String Manipulation Patterns techniques:

• Find Beautiful Indices in the Given Array II — Hard, same subpattern
• Repeated String Match — Medium, same subpattern
• Rotate String — Easy, same subpattern
• Shortest Palindrome — Hard, same subpattern
• Add Strings — Easy, same pattern
• Integer to Roman — Medium, same pattern