C++ | All approaches: brute force, Sliding Window | 12ms | map | Solution for Longest Substring
Dear All,\n\nI solved this issue with different approaches and happy to share with you. Probably looking to all of them and comparing you will understand which 
Dear All,\n\nI solved this issue with different approaches and happy to share with you. Probably looking to all of them and comparing you will understand which one is better and why. All solutions containes comments for your better understanding of algorithm. Hope you will enjoy =)\n\nPlease find below my last and best solution with Sliding Window approach. Here we have O(n) time complexity(where n is a length of string) and O(k) space complexity(where k is unique characters from the string). You can notice that find() takes additional affort and Time Complexity won\'t be equal to O(n). I will try to explain: In general Time Complexity of searching elements in map is O(log n) in worst case. But exactly in our case it\'s very close to O(1) because we add only unique characters and range of possible characters is very small compared to string length. Let\'s imagine that our string contains 1 000 000 characters. But in Hash Table will be maximum 128 characters(in real life even less because some specific characters won\'t not used). Method find() in our case will be O(log 128) = 7 - very close to constant time. So, on each step logic will do maximum 7 additional steps. That\'s why it\'s very close to O(n). We can say that TC is O(n * log m), where n - length of string, m - number of unique characters from string. But since we know that m not more than 128, and log m not more than 7 - is very close to constant and we can ignore it.\nWe can try to use unordered_map that TC of find is O(1). The reason why I use map instead - unordered_map is not stable. In worst case TC will be O(n), not O(1). It happens when hash function will generate same hash index that calls collisions. Also unordered_map required for extra space for Hash Table. map - always O(log n). Since we know that log n = 7 in worse case - make sense use map.\n```\nclass Solution {\npublic:\n    int lengthOfLongestSubstring(string s) \n    {        \n        // Return 0 if string is empty\n        if( s == "") { return 0; }\n        \n        // Hash table for storing characters and indexes\n        map<char, int> characters;       \n        \n        // Longest sequence that will be returned in the end: for sure will be > 1 because 0 result was checked in the beginning\n        int longest = 1;\n        int j = 0;\n        \n        // Each character from string add to HashTable with his index. If we reach same character again - update index\n        for (int i = 0; i < s.length(); ++i)\n        {\n            // If current character already exist in the HashTable  \n            if ( characters.find(s[i]) != characters.end() )\n            {\n                // Take larger index for future calculation between old and current+1 in HashTable\n                j = j >= characters.find(s[i])->second + 1 ? j : characters.find(s[i])->second + 1;\n            }\n            // Add character with current index to HashTable\n            characters[s[i]] = i;\n            // longest will be chosen between larger value: old longest OR current sequance between i and j indexes + 1\n            longest = longest >= i - j + 1 ? longest : i - j + 1;\n        }\n        \n        return longest;\n    }\n};\n```\n\nNext will be my first try with brute force solution that has O(n^3) complexity. This approach will work here in LeetCode for small strings, but for big you will receive status \'Time Limit Exceeded\'. In your IDE it will work even for big strings but very slowly. Iterator used just for practice. New method was created in private section for checking dublicates in substring - `bool dublicatesInSubstring(string& s, const int substringBegin, const int substringEnd)`.\n```\nclass Solution {\nprivate:\n    // Method for dublicates check in substring\n    bool dublicatesInSubstring(string& s, const int substringBegin, const int substringEnd)\n    {\n        std::map<char, int> charactersOfSubstr;\n        std::map<char, int>::iterator it;\n        \n        // Check substring for dublicates\n        for(int i = substringBegin; i <= substringEnd; ++i )\n        {\n            // Add character to HashTable\n            it = charactersOfSubstr.find(s[i]);\n            if ( it != charactersOfSubstr.end() )\n            {\n                it->second++;\n            }\n            else\n            {\n                charactersOfSubstr.insert(std::pair<char,int>(s[i], 0));\n            }\n            // In case HashTable has more that one such character - return true that means dublicates exist in substring\n            if( it->second > 0 )\n            {\n                return true;\n            }\n        }\n        \n        return false;\n    }\n    \npublic:\n    int lengthOfLongestSubstring(string s) \n    {\n        // Return 0 if string is empty\n        if( s == "") { return 0; }\n        \n        // Longest sequence that will be returned in the end\n        int longest = 0;\n        \n        // For each character from string - ckech longest sequence untin end of the string\n        for (int i = 0; i < s.length(); ++i)\n        {\n            for(int j = i; j < s.length(); ++j)\n            {\n                // In case no dublicates - function return false and longest substring should be calculated\n                if ( !dublicatesInSubstring(s, i, j) )\n                {\n                    longest = longest >= j - i + 1 ? longest : j - i + 1;\n                }\n            }\n        }\n        \n        return longest;\n    }\n};\n```\n\nMy next try was approach with O(n^2) complexity that much faster than previous and LeetCode finished all test cases without \'Time Limit Exceeded\' status. Iterator also used only for practice.\n```\nclass Solution {\npublic:\n    int lengthOfLongestSubstring(string s) \n    {        \n        // Return 0 if string is empty\n        if( s == "") { return 0; }\n        \n        std::map<char, int> charactersOfSubstr;\n        std::map<char, int>::iterator it;        \n        \n        // Longest sequence that will be returned in the end\n        int longest = 0;\n        \n        // For each character from string - check longest sequence until encountered dublicate\n        for (int i = 0; i < s.length(); ++i)\n        {\n            // HashTable should be cleared before starting with new substring analyzing\n            charactersOfSubstr.clear();\n            for(int j = i; j < s.length(); ++j)\n            {\n                // Try to find character in the HashTable\n                it = charactersOfSubstr.find(s[j]);\n                \n                // If current character already exist in the HashTable - quit from j-loop to get next character for analyze\n                if (it != charactersOfSubstr.end())\n                {\n                    break;\n                }\n                // If character doesn\'t exist in HashTable - add it and recount unique sequence lenght\n                else\n                {\n                    charactersOfSubstr.insert(pair<char, int>(s[j], 1));\n                                              \n                    // longest will be chose\u0442 between larger value: old longest OR current sequance (j - i + 1)\n                    longest = longest >= j - i + 1 ? longest : j - i + 1;\n                }                \n            }\n        }\n        \n        return longest;\n    }\n};\n```\n\nNext try was very close to O(n) but still loop inside loop used. After this approach I thought that it\'s possible to get rid of nested loop.\n```\nclass Solution {\npublic:\n    int lengthOfLongestSubstring(string s) \n    {        \n        // Return 0 if string is empty\n        if( s == "") { return 0; }\n        \n        // Hash table for storing characters and count dublicates\n        std::map<char, int> charactersOfSubstr;       \n        \n        // Longest sequence that will be returned in the end\n        int longest = 0;\n        int j = 0;\n        \n        // Each character from string add to HashTable: for dublicates increase value that used in result calculation\n        for (int i = 0; i < s.length(); ++i)\n        {\n            // Try to find character in the HashTable\n            // If current character already exist in the HashTable - increment value\n            if ( charactersOfSubstr.find(s[i]) != charactersOfSubstr.end() )\n            {\n                charactersOfSubstr.find(s[i])->second++;\n            }\n            // Othervise add it to HashTable\n            else\n            {\n                charactersOfSubstr.insert(pair<char, int>(s[i], 1));\n            }\n            \n            // ONLY if in HashTable exist several same characters:\n            // decrease ALL characters between j and i in HashTable AND increase j for calculation while s[i] value in Hash table > 1\n            while ( charactersOfSubstr.find(s[i])->second > 1 )\n            {\n                // Descrease value of existing character\n                charactersOfSubstr.find(s[j])->second--;\n                // Increase j for future calculation\n                ++j;\n            }\n            \n            // longest will be chosen between larger value: old longest OR current sequance (i - j + 1)\n            longest = longest >= i - j + 1 ? longest : i - j + 1;\n        }\n        \n        return longest;\n    }\n};\n```\n\nHope you read until the end and enjoyed =)\nIf you know how to improve the code - please let me know I will be very grateful.\nIf you like solution please vote - I will be pleased.\n\nThanks and have a good day.\n\nBest Regards, Yevhen.\n
['C', 'Sliding Window', 'Iterator', 'C++']