Shortest O(n) DP solution with explanations
/**\n     * Solution (DP, O(n)):\n     * \n     * Assume L[i] = s[m...i], denotes the longest substring without repeating\n     * characters that ends up at s[i
    /**\n     * Solution (DP, O(n)):\n     * \n     * Assume L[i] = s[m...i], denotes the longest substring without repeating\n     * characters that ends up at s[i], and we keep a hashmap for every\n     * characters between m ... i, while storing <character, index> in the\n     * hashmap.\n     * We know that each character will appear only once.\n     * Then to find s[i+1]:\n     * 1) if s[i+1] does not appear in hashmap\n     *    we can just add s[i+1] to hash map. and L[i+1] = s[m...i+1]\n     * 2) if s[i+1] exists in hashmap, and the hashmap value (the index) is k\n     *    let m = max(m, k), then L[i+1] = s[m...i+1], we also need to update\n     *    entry in hashmap to mark the latest occurency of s[i+1].\n     * \n     * Since we scan the string for only once, and the 'm' will also move from\n     * beginning to end for at most once. Overall complexity is O(n).\n     *\n     * If characters are all in ASCII, we could use array to mimic hashmap.\n     */\n\n    int lengthOfLongestSubstring(string s) {\n        // for ASCII char sequence, use this as a hashmap\n        vector<int> charIndex(256, -1);\n        int longest = 0, m = 0;\n\n        for (int i = 0; i < s.length(); i++) {\n            m = max(charIndex[s[i]] + 1, m);    // automatically takes care of -1 case\n            charIndex[s[i]] = i;\n            longest = max(longest, i - m + 1);\n        }\n\n        return longest;\n    }\n\n\nHope you like it :)
[]