java find the longest non-repeating substring- getting weird result

user_12106135 0
Viewed 185

I am doing one classic leet code problem: finding the longest non-repeating substring in a string. Though there are many similar problems on stack overflow. I scratched my head for hours couldn't know why my code produce this weird result. hoping that someone could tell me why my

I am doing it in Java

    public static void main( String[] args )
    {
        String s= "wwhoamiUrektxineabcdefghijklmno";
        longestNonRepeatStr(s);     
    }

    public static void longestNonRepeatStr(String tstring) {
        String str="";
        String compare="";
        List<String> list= new ArrayList<String>();
        int biggest =0;

        //find the nonrepeating string in each loop and add to list str
       for (int i=0; i<tstring.length(); i++) { 
        for (int j=i; j<tstring.length()-1; j++) {
            str+= tstring.charAt(j);
            compare= Character.toString(tstring.charAt(j+1));
            if (str.contains(compare)){
                list.add(str);
                str="";
                break;
            }
        }
    }

    //find the longest nonrepeating string in the list
       for (int i=0; i<list.size(); i++) {
        if (list.get(biggest).length()< list.get(i).length()) {
        biggest=i;
        }
    }

       System.out.println(list);    
       System.out.println(list.get(biggest));           
    }

For input string

"wwhoamiUrektxineabcdefghijklmno"

output is

"abcdefghijklmnb"

but it is wrong, the last letter should be "o"

java
5 Answers

You have several issues (see comments where I corrected the code):

public static void longestNonRepeatStr(String tstring) {
  String str="";
  String compare="";
  List<String> list= new ArrayList<String>();
  int biggest =0;

  for (int i=0; i<tstring.length(); i++) { 
    str = ""; // you must clear the current String before each iteration of the inner loop
    for (int j=i; j<tstring.length(); j++) { // here you were skipping the last character
      str+= tstring.charAt(j);
      // I improved the following condition
      if (j+1 < tstring.length() && str.contains(Character.toString(tstring.charAt(j+1)))){
        list.add(str);
        str="";
        break;
      }
    }
    if (str.length() > 0) { // if you finish the inner loop without breaking, you should
                            // add the current String to the List
      list.add(str);
    }
  }

  for (int i=0; i<list.size(); i++) {
    if (list.get(biggest).length()< list.get(i).length()) {
      biggest=i;
    }
  }

  System.out.println(list);    
  System.out.println(list.get(biggest));           
}

Or, as an alternative, you can add the current String to the List in the last iteration of the inner loop:

public static void longestNonRepeatStr(String tstring) {
  String str="";
  String compare="";
  List<String> list= new ArrayList<String>();
  int biggest =0;

  for (int i=0; i<tstring.length(); i++) { 
    str = "";
    for (int j=i; j<tstring.length(); j++) {
      str+= tstring.charAt(j);
      if (j+1 >= tstring.length() || str.contains(Character.toString(tstring.charAt(j+1)))){
        list.add(str);
        str="";
        break;
      }
    }
  }

  for (int i=0; i<list.size(); i++) {
    if (list.get(biggest).length()< list.get(i).length()) {
      biggest=i;
    }
  }

  System.out.println(list);    
  System.out.println(list.get(biggest));           
}

Further explanation of how you got the output "abcdefghijklmnb":

When i==16, your inner loop builds the String "abcdefghijklmn". Then it skips the "o", since you ended that loop prematurely (due to j<tstring.length()-1). This String is not yet added to the List, since you haven't detected a repeating character. Now when i==17, you append "b" to str and get "abcdefghijklmnb". Now you check if the next character "c" already appears in str, which is true, so you add "abcdefghijklmnb" to your List.

user_12215710

The problem here is the last iteration of you your loop structure:

for (int i=0; i<tstring.length(); i++) {
  for (int j=i; j<tstring.length() - 1; j++) {
    ...
  }
}

If we take your string wwhoamiUrektxineabcdefghijklmno, then when i=30 it'll be processing the last character of the string ("o"), however the length of tstring is 31 so the next line (your nested for loop) will not run as int j=30 and tstring.length() - 1 = 30

Instead you should just start your next for loop at int j = i + 1 and let it run to tstring.length()

There are also some logic problems as to when you are adding characters to your string and when you decide that the string needs to be added to your list. Here try this... 

for (int i = 0; i < tstring.length(); i++) {
  str += tstring.charAt(i);
  for (int j = i + 1; j<tstring.length(); j++) {
    compare= Character.toString(tstring.charAt(j));
    if (str.contains(compare)){
        break;
    } else {
        str += tstring.charAt(j);
    }
  }
  list.add(str);
  str = "";
}

Finally, you don't need str to be external to your loop. You can instantiate it in your loop (it'll save you about 2 lines of code).

user_120891830

When j reaches the end of the input string without finding a repeated character, you don't add the substring to the list, and you don't reset str.

Try something like this:

    for (int i = 0; i < tstring.length(); i++) {
        String str = Character.toString(tstring.charAt(i));
        for (int j = i + 1; j < tstring.length(); j++) {
            char c = tstring.charAt(j);
            if (str.indexOf(c) >= 0) {
                break;
            }
            str += c;
        }
        list.add(str);
    }
user_70364190

The problem is in the nested for when you are in the last cycle task. If the if doesn't match you don't add the str to list and you don't resent str variable. In order to solve the problem I changed a little bit your source code:

 public static void longestNonRepeatStr(String tstring) {
        String str="";
        String compare="";
        List<String> list= new ArrayList<String>();
        int biggest =0;

        //find the nonrepeating string in each loop and add to list str
       for (int i=0; i<tstring.length()-1; i++) { 
        for (int j=i+1; j<tstring.length(); j++) {

            str+= tstring.charAt(j-1);
            compare= Character.toString(tstring.charAt(j));
            if (str.contains(compare)){
                list.add(str);
                str="";
                break;
            }else{
                if (j==tstring.length()-1){
                    str+= tstring.charAt(j);
                    list.add(str);
                    str="";
                }
            } 
         }
       }

       //find the longest nonrepeating string in the list
       for (int i=0; i<list.size(); i++) {
        if (list.get(biggest).length()< list.get(i).length()) {
           biggest=i;
        }
       }

       //System.out.println(list);    
       System.out.println(list.get(biggest));      
}
user_56191930

For finding the longest nonrepeating substring, you do not need to find (and thus: test) all of them.

You could send a "worm" along the string: it grows (head proceeds) as long as it does not contain repeats, then it shrinks (tail proceeds) as long as there is a repeat.

String s = "wwhoamiUrektxineabcdefghijklmno";
String t = "                               ";

int head = 0, tail = 0;
String worm = "";
String caterpillar = "";
do {
    while (head < s.length() && worm.indexOf(s.charAt(head)) < 0) {
        head++;
        worm = s.substring(tail, head);
        System.out.println(t.substring(0, tail) + worm);
        if (worm.length() > caterpillar.length())
            caterpillar = worm;
    }
    if (head < s.length())
        while (worm.indexOf(s.charAt(head)) >= 0) {
            tail++;
            worm = s.substring(tail, head);
            System.out.println(t.substring(0, tail) + worm + "(" + s.charAt(head) + ")");
        }
} while (head < s.length());
System.out.println("Longest: " + caterpillar);

Test: https://ideone.com/yMebjx
Output:

w
 (w)
 w
 wh
 who
 whoa
 whoam
 whoami
 whoamiU
 whoamiUr
 whoamiUre
 whoamiUrek
 whoamiUrekt
 whoamiUrektx
  hoamiUrektx(i)
   oamiUrektx(i)
    amiUrektx(i)
     miUrektx(i)
      iUrektx(i)
       Urektx(i)
       Urektxi
       Urektxin
        rektxin(e)
         ektxin(e)
          ktxin(e)
          ktxine
          ktxinea
          ktxineab
          ktxineabc
          ktxineabcd
           txineabcd(e)
            xineabcd(e)
             ineabcd(e)
              neabcd(e)
               eabcd(e)
                abcd(e)
                abcde
                abcdef
                abcdefg
                abcdefgh
                abcdefghi
                abcdefghij
                abcdefghijk
                abcdefghijkl
                abcdefghijklm
                abcdefghijklmn
                abcdefghijklmno
Longest: abcdefghijklmno

The character in parenthesis is the one having a duplicate in the shrinking phase.
Of course the implementation would be simpler and faster without the printing, for example the String-s could be eliminated completely, the entire algorithm could work with indices on a char[] (at the price of having a loop instead of indexOf()).

user_79164380
Related