Sunday, May 29, 2016

longest continuous substring with unique characters

On repeating char, start again from index after the 1st occurrence.
s: abcade
   |--|
    |----|5

s: abbded
   |-|
     |--|3
       |-|

s: aa
   ||1
    ||

s: abc
   |--|3
(s):
    if s == null:
        throw
    if s == "":
        return ""
    maxend = maxstart = 0
    map ctoimap = new //char->index
    start = i = 0
    while i < s.length():
        c = s[i]
        if ctoimap.haskey(c):
            if i-start > maxend-maxstart:
                maxend = i, maxstart = start
            i = start = ctoimap[c] +1
            ctoimap.clear()
        else:
            ctoimap[c] = i
            i++
    if i-start > maxend-maxstart:
        maxend = i, maxstart = start
    return s.substring(maxstart, maxend-maxstart)
[Hat tip to SM]

1 comment:



  1. private static String extractMap(Map map){

    StringBuffer sB = new StringBuffer();
    Iterator it = map.entrySet().iterator();

    while(it.hasNext()){
    //Map.Entry.
    Map.Entry entry = (Map.Entry) it.next();
    sB.append(entry.getKey());
    }

    return sB.toString();
    }

    private static String processMap(String input){

    Map repeatMap = new LinkedHashMap<>();
    int i = 0;

    String longString = "";
    do{

    if(!repeatMap.containsKey(input.charAt(i))){
    repeatMap.put(input.charAt(i),i);
    }
    else{

    int val = repeatMap.get(input.charAt(i));
    i = val;
    String retString = extractMap(repeatMap);
    repeatMap.clear();
    if(longString.length() < retString.length()){
    longString = retString;
    }
    }
    i++;

    }while(i < input.length());

    return longString;
    }

    ReplyDelete