fail case: assertEquals("bcd", new MaxSubStringTDD().match("abxbcd", "abcd"));

[simshi]

expected: [bcd] but was ab because there is no backtrack in current implementation, code should be revised to:

if (!longStr.contains(partial)) {
    return matchPartialShortStr(longStr, shortStr, index + 1 - partial.length() + 1, "", result);

but it falls back to O(M*N)? @JosephYao any comment?

[JosephYao]

The test case makes sense. But, I have a different implementation (with some refactoring). :)

    String currentChar = shortStr.substring(0, 1);
    String candidate = matched + currentChar;
    if (longStr.contains(candidate)) {
        result = max(candidate, result);
        matchPartialShortStr(longStr, shortStr.substring(1), candidate);
    }

    if (longStr.contains(currentChar) && !candidate.equals(currentChar)) {
        matchPartialShortStr(longStr, shortStr, "");
    } else {
        matchPartialShortStr(longStr, shortStr.substring(1), "");
    }

My O(n) knowledge is limited. @simshi , do you know what's that for the code above? I feel it's still fast than O(M*N)