solution.cpp

int max(int a, int b) {
    return (a > b ? a : b);
}

class Solution {
public:
    int withIndex(string s, int start_index, int end_index) { 
        //base case
        if(end_index == start_index)
            return 1;
        if(end_index - start_index == 1) {
            if(s[start_index] == s[end_index])
                return 1;
            else
                return 2;
        }
        
        int middle_index = (start_index + end_index) / 2;
        int right_answer = withIndex(s, middle_index, end_index);
        int left_answer = withIndex(s, 0, middle_index);
        
        int best_answer = max(right_answer, left_answer);
        unordered_set<char> so_far;
        
        // Case 1: First right then left 
        so_far.clear();
        int current_index = middle_index;
        while(true and current_index <= end_index) {
            if(so_far.find(s[current_index]) == so_far.end())
                so_far.insert(s[current_index]);
            else
                break;
            current_index++;
        }
        current_index = middle_index-1;
        while(true and current_index >= start_index) {
            if(so_far.find(s[current_index]) == so_far.end())
                so_far.insert(s[current_index]);
            else
                break;
            current_index--;
        }   
        
        best_answer = max(best_answer, so_far.size());
        
        // Case 2: First left then right
        so_far.clear();
        current_index = middle_index-1;
        while(true and current_index >= start_index) {
            if(so_far.find(s[current_index]) == so_far.end())
                so_far.insert(s[current_index]);
            else
                break;
            current_index--;
        }   
        current_index = middle_index;
        while(true and current_index <= end_index) {
            if(so_far.find(s[current_index]) == so_far.end())
                so_far.insert(s[current_index]);
            else
                break;
            current_index++;
        }
        
        best_answer = max(best_answer, so_far.size());
        
        return best_answer;
    }
    int lengthOfLongestSubstring(string s) {
        if(s.length() == 0)
            return 0;
        
        return withIndex(s, 0, s.length() - 1);
    }
};