4
\$\begingroup\$

This is the code I came up with.It seems correct.

I am interested in:
1) Improvements on code
2) How can it be better than this? i.e. this is O(N^2) Could I have done better in complexity? What should I have read to do it?

Thanks

 public int lengthOfLongestSubstringNoRepetitions(String s) {

            if(s == null || s.trim().equals(""))
                return 0;

            Map<Character,Boolean> seen = new HashMap<Character,Boolean>();

            int max = Integer.MIN_VALUE;

            for(int i = 0; i < s.length(); i++){
                for(int j = i; j < s.length(); j++){
                    char c = s.charAt(j);
                    if(seen.containsKey(new Character(c))){
                        //duplicate in substring                    
                        int tmp = j - i;
                        if(max < tmp) max = tmp;
                        break;
                    }
                    else{
                        seen.put(new Character(c),true);
                        if(j == s.length() -1){
                            //Reached the end of string.Add one to get the range
                            if(max < (j - i + 1)) max = (j - i + 1);    
                        }
                    }                
                }
                seen.clear();
            }

            return (max == Integer.MIN_VALUE)?s.length():max;

        }
\$\endgroup\$
5
\$\begingroup\$

Here's an O(n) solution. It replaces the Map with a char-indexed vector of the index where each char was last seen.

public static int lengthOfLongestSubstringNoRepetitions(String s) {

    if (s == null)
        return 0;

    // Trimming input even for the non-empty case is more consistent.
    final String str = s.trim();

    if (str.equals(""))
        return 0;

    int seen[] = new int[Character.MAX_VALUE+1];
    for (int i = 0; i <= Character.MAX_VALUE; ++i)
        seen[i] = -1;

    int max = 1;
    int len = 0;

    for (int j = 0; j < str.length(); ++j) {
        char ch = str.charAt(j);
        // If ch was recently seen,
        // counting must restart after the last place it was seen.
        // Otherwise, it adds 1 to the length.
        len = Math.min(j-seen[ch], len+1);
        if (len > max)
            max = len;
        seen[ch] = j;
    }
    return max;
}
\$\endgroup\$
  • \$\begingroup\$ +1 by me thank you. I will study this.Is this a standard approach?Where could I read about such techniques? \$\endgroup\$ – user384706 Feb 20 '12 at 16:23
  • \$\begingroup\$ 1. You have forgotten all type casting. 2. The question was to find the longest substring, not its length. 3. You have forgotten to give a reference to this very algorithm description that appeared here 2 days before. \$\endgroup\$ – Gangnus Feb 23 '12 at 13:12
  • \$\begingroup\$ @Gangnus 1. Where/why would a cast be needed? 2. The OP title was longest substring, the function of the OP code was only its length. 3. I should have ack'ed the prior answer's common feature, the vector of offsets indexed by char. But it would have been wrong to claim to be using "the very algorithm". So much of the other detail in that answer -- start indexes and lists of substrings and even casts -- didn't enter into my algorithm at all. The code added later to clarify that answer confirms the difference in the algorithms. \$\endgroup\$ – Paul Martel Feb 23 '12 at 16:22
  • \$\begingroup\$ 1. you can't simply use char as int, or we use different Java -- 2. Yes, the questioner has to choose, what he wants exactly. So, he has both variants. 3. Ah. After moving the start point, you restart, and so throw away the info already got... And you think, that such deterioration of the algorithm is enough to consider this variant as original? It is up to you. \$\endgroup\$ – Gangnus Feb 23 '12 at 17:11
  • \$\begingroup\$ @Gangnus 1. javac 1.6.0_23 likes this use of char as a small unsigned value. I highly recommend it for readability. -- 2. Agreed, but not much of a choice since both answers are identical and one is deteriorated -- or so I'm told. -- 3. I'm not claiming "originality", just significant difference from the alternative as described earlier and expanded later, an alternative that I am still trying to understand, to see if I can upvote it in good conscience. \$\endgroup\$ – Paul Martel Feb 23 '12 at 21:13
2
\$\begingroup\$

Expression s.equals("") is a bad practice. It should be "".equals(s) if you are comparing const and string. Class String also has method isEmpty().

\$\endgroup\$
2
\$\begingroup\$

I think, that after founding the first char that is present in the substring being checked, you should not stop checking it, but cut off the part up to the first appearance of the char, add to the second appearance and continue to check the string. So the algorithm remains be O(n^2), but will be faster anyway.

The other (additional) possibility to fasten the algorithm is to make an integer array address[2^16] that will have address of every char in that current substring. So you don't have to seek into the substring, but can take the address at once from the array. So, the difficulty becomes O(n).

Make empty list of possibly longest substrings. Make all address[i]=-1;

Keep substring as a pair of start/end indexes in the source string. Start from them both=0;

with every newChar on position iPosition you check, if it is already in the substring. So, that simply check currentArrdess=address[(long)newChar].

If currentArrdess=0, you add the newChar to the current substring. Increase end index and put address[(long)newChar]=endIndex;

If currentArrdess>0, remember the current sunstring into the list of possibly longest substring and after that use currentArrdess+1 as a new start index.

String findLongestSubstr(String source){
    final int charsNum=2^16;
    int[] address=new int[charsNum];
    int startSubstr= 0;
    int endSubstr= -1;
    ArrayList<String> pretendents=new ArrayList<String>();
    for (int i=0; i<charsNum; i++) address[charsNum]=-1;
    // find all pretendents
    while(endSubstr<source.length()-1){
        endSubstr++;
        int currentCharInt=source.charAt(endSubstr);
        if(address[currentCharInt]>=0) {
            // old char - 
            int newStartSubstr=address[currentCharInt]+1;
            //remove addresses up to (inclusive) the first appearance of the current char 
            for(int i=startSubstr; i<=address[currentCharInt];i++) {
                address[(int)source.charAt(i)]=-1;
            }
            // remember the string already found, before cutting it
            pretendents.add(source.substring(startSubstr, endSubstr+1));
            // cut the currently being checked string from the start
            startSubstr=newStartSubstr;
        }
        address[currentCharInt]=endSubstr;
    }
    // find max length pretendent
    ...
}
\$\endgroup\$
  • \$\begingroup\$ +1 by me thank you I will study this.Is this a standard approach?Where could I read about such techniques? \$\endgroup\$ – user384706 Feb 20 '12 at 16:22
  • \$\begingroup\$ Yes, remembering something instead of counting it many times is a standard technology. I don't think, there is books on exactly this theme, but as for optimization and algorithms, the classic book is Knuth (here www-cs-staff.stanford.edu/~uno/taocp.html is the bibliography). \$\endgroup\$ – Gangnus Feb 20 '12 at 21:10
1
\$\begingroup\$

It won't make a huge difference but you could use a Set instead of a Map, since all the values in your Map are true, and therefore not very useful.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.