☕ DSA Java Articles

Topics › Strings › Medium String Problems

Implement ATOI/STRSTR

Medium TUF ID 2861 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

This entry of the SDE sheet bundles two classic “re-implement the library function” questions. Interviewers ask either one, so both are covered here.

Part A, atoi (LeetCode 8). Convert a string to a 32-bit signed integer with these exact rules:

  1. Skip leading space characters ' '.
  2. Read an optional single sign, '+' or '-'.
  3. Read digits until the first non-digit character or the end of the string. Leading zeros are allowed.
  4. If no digits were read, the result is 0.
  5. If the value is outside [-2^31, 2^31 - 1], clamp it to the nearest bound.

Part B, strStr (LeetCode 28). Given haystack and needle, return the index of the first occurrence of needle in haystack, or -1 if it does not occur. By convention an empty needle occurs at index 0.

Constraints: atoi input has length up to 200; for strStr, 1 ≤ n, m ≤ 10^4 on LeetCode. The Java methods also accept empty strings.

Example 1

atoi("   -042")       = -42           // spaces skipped, sign read, leading zero ignored
atoi("1337c0d3")      = 1337          // parsing stops at 'c'
atoi("-91283472332")  = -2147483648   // below the int range, clamped

Example 2

strStr("sadbutsad", "sad") = 0        // first of two occurrences
strStr("leetcode", "leeto") = -1      // never occurs

Approach 1: atoi, one careful left-to-right scan

Intuition. There is nothing algorithmically deep here; the problem tests whether you can follow a specification precisely and handle overflow without cheating. The rules describe a tiny state machine (spaces, then sign, then digits, then stop), and a single index i walking forward implements it directly.

The interesting part is overflow. We build the value with result = result * 10 + d, and that expression itself can overflow an int. So we must decide before the multiplication whether it would leave the range. Integer.MAX_VALUE is 2147483647 = 214748364 × 10 + 7. The next step overflows exactly when result > 214748364, or when result == 214748364 and the new digit is greater than 7.

The same test works for negative numbers, which is not obvious at first. We accumulate the magnitude as a positive number. The most negative value, -2147483648, has magnitude 214748364 × 10 + 8, so the test fires for it and we return Integer.MIN_VALUE, which is precisely the right answer anyway. Every magnitude larger than that also clamps to MIN_VALUE.

Algorithm.

  1. Advance i past spaces.
  2. If s[i] is '+' or '-', record the sign and advance once.
  3. While s[i] is a digit d: if appending d would exceed Integer.MAX_VALUE, return the bound for the current sign; otherwise result = result * 10 + d.
  4. Return sign * result.
static int myAtoi(String s) {
    int i = 0, n = s.length();
    while (i < n && s.charAt(i) == ' ') i++;                // 1. skip leading spaces
    int sign = 1;
    if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
        if (s.charAt(i) == '-') sign = -1;                  // 2. at most one sign character
        i++;
    }
    int result = 0;
    while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {   // 3. digits until the first non-digit
        int d = s.charAt(i) - '0';
        // 4. would result * 10 + d exceed Integer.MAX_VALUE? (MAX_VALUE = 214748364 * 10 + 7)
        if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && d > 7)) {
            return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }
        result = result * 10 + d;
        i++;
    }
    return sign * result;
}

Complexity. Time O(n): each character is looked at once. Space O(1).

Two details worth copying. First, the digit test is c >= '0' && c <= '9', not Character.isDigit(c), because isDigit also accepts digits from other scripts (such as the Arabic-Indic three), and c - '0' would give nonsense for them. Second, only ' ' counts as leading whitespace in this problem; tabs or newlines stop the parse with result 0.

An alternative is to accumulate in a long and clamp as soon as the value passes 2^31. That works because we stop before the long itself can overflow, but the int-only check above is what interviewers usually want to see, since it shows you understand where overflow comes from.

Approach 2: strStr brute force

Intuition. Try every possible starting position start in the haystack (there are n - m + 1 of them) and compare the needle character by character. Stop at the first mismatch, or report start if all m characters matched.

Algorithm.

  1. For start = 0 .. n - m:
  2. Count how many characters match: k advances while haystack[start + k] == needle[k].
  3. If k == m, return start.
  4. Return -1.
static int strStrBruteForce(String haystack, String needle) {
    int n = haystack.length(), m = needle.length();
    for (int start = 0; start + m <= n; start++) {
        int k = 0;
        while (k < m && haystack.charAt(start + k) == needle.charAt(k)) k++;
        if (k == m) return start;                           // all m characters matched
    }
    return -1;
}

Complexity. Time O(n · m) in the worst case, space O(1).

The worst case needs many near-misses. For haystack = "aaaa...ab" and needle = "aa...ab", every start matches almost the whole needle before failing on the b, so the work is about n · m. On random text the first mismatch comes quickly and the brute force is effectively linear, which is why library implementations often use it.

Notice the waste: after matching aaa and failing, the brute force moves to the next start and compares those same as again, even though it already knows what they are.

Approach 3: strStr optimal, KMP

Intuition. When a mismatch happens after matching k characters, we know the last k haystack characters exactly: they equal needle[0..k). The question “where could the next match start?” therefore depends only on the needle, and can be precomputed. The answer is the longest proper prefix of needle[0..k) that is also a suffix of it. That much of the needle is already matched at the new alignment, so we keep it and never move the haystack pointer backwards.

This precomputed table is the LPS (longest proper prefix which is also suffix) array, also called the prefix function. For needle = "aab", lps = [0, 1, 0]: after matching "aa", a mismatch lets us keep one a.

Building the LPS array is the same matching process run on the needle against itself: len is the length of the prefix matched so far, and on a mismatch we fall back to lps[len - 1], the next-shorter border.

Algorithm.

  1. Build lps for the needle.
  2. Scan the haystack with index i and matched count k.
  3. While k > 0 and haystack[i] != needle[k], set k = lps[k - 1].
  4. If haystack[i] == needle[k], increment k. If k == m, return i - m + 1.
  5. Return -1.
static int strStrKmp(String haystack, String needle) {
    int n = haystack.length(), m = needle.length();
    if (m == 0) return 0;
    int[] lps = buildLps(needle);
    int k = 0;                                              // characters of needle matched so far
    for (int i = 0; i < n; i++) {
        while (k > 0 && haystack.charAt(i) != needle.charAt(k)) k = lps[k - 1];
        if (haystack.charAt(i) == needle.charAt(k)) k++;
        if (k == m) return i - m + 1;
    }
    return -1;
}

/** lps[i] = length of the longest proper prefix of p[0..i] that is also a suffix of p[0..i]. */
static int[] buildLps(String p) {
    int[] lps = new int[p.length()];
    int len = 0;                                            // length of the current matched prefix
    for (int i = 1; i < p.length(); i++) {
        while (len > 0 && p.charAt(i) != p.charAt(len)) len = lps[len - 1];
        if (p.charAt(i) == p.charAt(len)) len++;
        lps[i] = len;
    }
    return lps;
}

Dry run on haystack = "aaaaab", needle = "aab", lps = [0, 1, 0]:

i haystack[i] k before fallback k after
0 a 0 none 1
1 a 1 none 2
2 a 2 needle[2] = b mismatch, k = lps[1] = 1 2
3 a 2 same as above 2
4 a 2 same as above 2
5 b 2 none 3, return 5 - 3 + 1 = 3

Complexity. Time O(n + m). In the matching loop k increases at most once per character of the haystack, and every fallback strictly decreases it, so the total number of fallbacks is at most n. The same argument bounds the LPS construction by O(m). Space O(m) for the LPS array.

Edge cases and pitfalls