CareerCup

static void Main(string[] args)
        {
            int[] a = new int[26];
            int count = 0, min = 0, max=0;
            string s = "hello";
            for (int i = 0; i < 26; i++)
                a[i] = -1;
            for (int i = 0; i < s.Length; i++)
                if (a[s[i]-97] < min)
                {
                    a[s[i] - 97] = i;
                    count++;
                    if (count > max)
                        max = count;
                }
                else
                {
                    count -= a[s[i] - 97];
                    min = a[s[i] - 97] + 1;
                }
            Console.WriteLine(max);
            Console.ReadLine();
        }

def longest_substr_with_uniq_char(str)
  return "" if (str.size == 0)

  splits = str.split("")
  uniq_char_str = splits[0]
  longest = uniq_char_str

  splits[1..-1].each do |ch|
    if (!uniq_char_str.include?(ch))
      uniq_char_str << ch
    else
      uniq_char_str = ch
    end

    if (uniq_char_str.length > longest.length)
      longest = uniq_char_str
    end
  end

  longest
end

public int lengthOfUniqueSubstring(String s) {
		
		if(s.length() == 0) return 0;

		// assuming ASCII characters
		boolean[] alphabet = new boolean[256];
		
		int c = 0;
		int lastMax = 0;
		for (int i = 0; i < s.length(); i++) {
			if(alphabet[s.charAt(i)] == false){
				alphabet[s.charAt(i)] = true;
				c++;
			} else {
				if(lastMax < c) lastMax = c;
				c = 0;
				alphabet = new boolean[256];
				i--;
				continue;
			}
		}
		
		return (lastMax<c)?c:lastMax;
	}

This solution keeps a map of the last occurrence of each letter and watches the subset's length from the position of the last duplicate (start of new subset).

public static int returnLongestUniqueSubset (String input)
	{
		//create hashmap to track last occurrence of each letter
		HashMap<Character, Integer> letters = new HashMap<Character, Integer>();

		int maxLength = 0;
		int lastDup = 0;			//position of last duplicate seen

		for (int i=0;i<input.length();i++)
		{
			//if letter hasn't been seen before, put its position in hm
			if(!letters.containsKey(input.charAt(i)))
			{
				letters.put(input.charAt(i), i);
			}
			//if it has been seen, update last duplicate to current pos and re-enter item in hm
			else
			{
				lastDup = i;
				letters.put(input.charAt(i), i);
			}
			//check to update max length
			if (maxLength < i-lastDup+1)
			{
				maxLength = i-lastDup+1;
			}
		}
		System.out.println(maxLength);
		return maxLength;
	}

runtime: O(n)
in action here: https://ideone.com/9CB7he

There are two tasks to be solved: first, mark occurence of character in a substring and second, scan the whole string while tracking the maximum lenght.
(i) Assuming that the string was ASCII one can use a boolean array of the size 128 in order to mark characters present in a substring.
(ii) We can use two array indexes defining the substring, 'left' and 'right' both starting at position zero. Both indexes can only increment at the time. When 'right' index increments, the new character is added to the substring and marked as present in via boolean array. If the left index increments a character is removed from a substring and unmarked in boolean array.
(iii) The last question is how do we increment indexes. Check char at 'right' and if not present, mark it and increment 'right'. However, if char at 'right' is present, increment unmark char at 'left' and increment.

A sample code is shown below:

public int maxlenSubstring(String s) {
	int N = s.length();
	int maxlen = 0;
	boolean[] h = new boolean[128]; 		// ASCII, java inits to false

	for (int k = 0, i = 0, j = 0; i < N; k++) {
		if (!h[s.charAt(i)])		h[s.charAt(i++)] = true;
		else						h[s.charAt(j++)] = false;
		if(maxlen < i-j) 			maxlen = i-j;
	}
	
	return maxlen;
}

Below solution takes O(n) time.

static int longestUniqueSubString(String s){
		int length = 0;
		if(s==null || (length = s.length())==0)
			return 0;
		int startIndex = 0,subStringLength=0;
		HashMap<Character,Integer> map = new HashMap<Character,Integer>();
		
		
		for (int i = 0; i < length; i++) {
			char c = s.charAt(i);
			if(map.containsKey(c) && map.put(c, i) >= startIndex){
			
				if((i-startIndex) > subStringLength){
					subStringLength=(i-startIndex);
				}
				startIndex = i;
			}
			else{
				map.put(c, i);
			}
		}
		// if all characters are unique
		if(subStringLength==0){   
			subStringLength= s.length();
		}
		return subStringLength;
	}

Step 1: Maintain a 256 integer array to store position of last visited character.
Step 2: start from beginning. Check last visited position of char in array.
Step 3: if position is less than the start it means the char is not found in current substring so continue
Step 4: Is position is more than start from there

private static void longestSubstr(String string) {
		
		// TODO Auto-generated method stub
		if(string == null || string.trim().length() <=0){
			return;
		}
		
		Queue<Integer> lenQ = new LinkedList();
		int[] placeSet = new int[256];
		int start =0;
		int len =1;

		for(int i=0;i<string.length();i++){ 
			if(placeSet[string.charAt(i)] < start) {
				placeSet[string.charAt(i)] =i;
			} else {
				start = placeSet[string.charAt(i)]+1;
				placeSet[string.charAt(i)] = i;
			}
			if((i-start+1) > len) {
				len = i-start+1;
				lenQ.clear();
				lenQ.add(start);
			} else if((i-start+1) == len){
				lenQ.add(start);
			}
		}
		
		while(!lenQ.isEmpty()){
			int startStr = lenQ.remove();
			System.out.println(" longest String : "+startStr +" length "+len);
			for(int i=0;i<len;i++)
			System.out.print(string.charAt(startStr+i));
		}
		
		return ;
	}

public void longestSubstring(string str1)
        {
            if(str1.Length < 1)
            {
                Console.WriteLine("string is empty");
                return;
            }
            // to store the previous character index value
            int[] characterIndex = new int[256]; 
            int maxlength, startMaxIndex,currentIndex,lastMaxIndex ;
            maxlength = startMaxIndex = currentIndex = lastMaxIndex = 0;

            while(currentIndex < str1.Length)
            {
                // To set the uquine character condition
                bool[] isRepeat = new bool[256]; 
                int count, start, last, j;
                last = count = 0;
                start = j = currentIndex; 
                bool repeatresult = false;

                // Condition to verify substring with unqiue characters 
                while (!repeatresult && j <= str1.Length -1) 
                {
                    if (j == str1.Length - 1)
                        currentIndex = j+1;

                    int charvalue = str1[j];
                    //condition Verifying the unqiue character
                    if (isRepeat[charvalue] == false )  
                    {
                        // update index value where the character is seen in string
                        characterIndex[charvalue] = j;   
                        isRepeat[charvalue] = true;
                        last = j;  // tracking the last character position in current loop 
                        count++;   // tracking the count of unqiue characters
                        j++;       
                    }
                    else
                    {
                        // setting the current index value to the previous occurance of the non-unqiue character for search of next unqiue sub string      
                        currentIndex = characterIndex[charvalue] + 1;   
                        characterIndex[charvalue] = j;
                        last = j - 1;  // tracking the last unique character position in current loop 
                        repeatresult = true;
                    }
                }
                // check for max lenght
                if (count > maxlength)
                {
                    // setting the max length sub string index value
                    maxlength = count;
                    startMaxIndex = start;
                    lastMaxIndex = last;
                }

            }

            //Print the sub string
            Console.WriteLine(" SubString Max length = {0} ", maxlength);
            while (startMaxIndex <= lastMaxIndex)
            {
                Console.Write(str1[startMaxIndex]);
                startMaxIndex++;
            }

        }

object LongestUniqueSubstring {

  val input = "aaabcaaabded"

  def main(args: Array[String]) {
    println(lus(input))
  }

  def lus(s: String) = {
    var maxSubstring = ""
    for (i <- 0 until s.length) {
      val longestPrefix = lup(s.substring(i))
      if (maxSubstring.length < longestPrefix.length) {
        maxSubstring = longestPrefix
      }
    }
    maxSubstring
  }

  //longest unique chars prefix
  var lubArr: Array[Boolean] = null
  private def lup(s: String): String = {
    lubArr = new Array[Boolean](256)
    var index = 0
    var ret = new StringBuilder()
    while (index < s.length) {
      if (!lubArr(s.charAt(index))) {
        ret.append(s.charAt(index))
        lubArr(s.charAt(index)) = true
        index += 1
      } else {
        return ret.toString
      }
    }
    return ret.toString
  }
}

Keep a map storing the last occurrence of each character in the original sequence.

Whenever you stumble upon a character that is already present in the subsequence you are considering, reset the start position of the subsequence to the index right after the last occurrence of this conflicting character.

Every time you find a character that can be added to the subsequence, check if the new length is better than the best length so far.

#include <string>
#include <map>

int longest(const std::string &word)
{
	if (word.empty()) return 0;

	std::map<char, int> last_occurrence;

	for (const char &c: word) {
		last_occurrence[c] = -1;
	}

	int i, start = 0, length = 1, best_length = 1;
	last_occurrence[word[0]] = 0;

	int n = word.length();
	for (i = 1; i < n; ++i) {
		int c = word[i];
		int lo = last_occurrence[c];

		if (lo >= start) {
			start = lo + 1;
			length = i - start + 1;
		}
		else {
			++length;
			if (length > best_length)
				best_length = length;
		}

		last_occurrence[c] = i;
	}

	return best_length;
}