# Index of a substring

Question: Write a function that returns the index of where a substring begins within a given string. Return -1 if it doesn't exist.

Related Tags:

## Linear Approach

A brute force approach to this problem would be to line up the substring beginning at each character in our string, until a match is found. This approach is simple and easy to understand.

## Algorithm Pseudocode

Here's what the algorithm looks by, step-by-step.

1. Loop through each character `c` of our `str` (that fits our `substr`).
2. Within this loop, line up each character in the `substr`, starting with at `c`.
3. If any characters do not match, break out and move onto the next character in `str`.
4. If we are able to loop through to our last character in substr, return the index of where we started our search in the `str`.
5. Otherwise, we have exhausted our search so return `-1`.

## Efficiency

The time complexity is O(mn) where m is the length of the substring and n is the length of the string. Space complexity is O(m+n), simplified to O(n) since the length of our string is always greater than the substring.

## Implementation in Java

``````static int substrIndex(String str, String substr) {

// Can't have a substring longer than the string itself
if (substr.length() > str.length()) {
return -1;
}

// iterate through our string until substr that lines up
char[] strArray = str.toCharArray();
char[] substrArray = substr.toCharArray();

// Only up to where our substr can fit
for (int i = 0; i <= strArray.length - substrArray.length; i++) {
for (int j = 0; j < substrArray.length; j++) {

if (strArray[i+j] != substrArray[j]) {
break;
}

// Last char lined up, success!
if (j == substrArray.length - 1) return i;

}

}

return -1;

}
``````

Came up with a better solution or have a question? Comment below!

Next Challenge: