**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:

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.

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

- Loop through each character
`c`

of our`str`

(that fits our`substr`

). - Within this loop, line up each character in the
`substr`

, starting with at`c`

. - If any characters do not match, break out and move onto the next character in
`str`

. - 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`

. - Otherwise, we have exhausted our search so return
`-1`

.

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.

```
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: Generating a list of primes less than n