Sunday, October 30, 2016

Leetcode 3: Longest Substring Without Repeating Characters

Problem statement could be found @https://leetcode.com/problems/longest-substring-without-repeating-characters/

Code Snippet -


class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        long start = 0;
        long current =0;
        long arr[256];
        for (int i=0;i<256;i++)
            arr[i]= -1;
        int maxL = 0;
       
        while(current < s.size()){
            int x = s.at(current);
         
            // if character has already occurred
            if (arr[x] != -1 ){
                // if the current character, has just repeated
                if ( ( arr[x] +1) == current){
                    start = current;
                }else{
                    // to handle string like "abcdbx", here second occurence of b changes the start index
                    if (start <= arr[x])
                        start = arr[x] +1;
                   
                }
            }
            if ((current-start+1) > maxL){
                 maxL = current-start+1;
            }
            arr[x] = current;
           
            current++;
        }
     
        return maxL;
    }
};