[Week Six] Programming Contest - Longest Substring

General Discussion Off Topic
1

Welcome back to week six of the weekly programming contests! If you are new to the contest or need a refresher don’t forget to read up on the rules and information Posted Here

This weeks challenge is to implement the method public static String longest(String s) (The method can be renamed). This method returns the longest substring of the given String which does not have any repeating characters. You can ignore case for this challenge (assume input will be lowercase).

Examples:

longest(“aaaaa”) -> “a”
longest(“ababab”) -> “ab”
longest(“abcdeabcde”) -> “abcde”
longest(“sponge”) -> “sponge”
longest(“spongepowered”) -> “sponge”
longest(“antidisestablishmentarianism”) -> “blishmentar”
longest(“pneumonoultramicroscopicsilicovolcanoconiosis”) -> “noultramic”
longest(“i like to eat pie”) -> “like to”
longest(“i don’t like pie”) -> “don’t like”

EDIT: If there are multiple valid answers, you can return either one.

Imports are allowed for this challenge!

Challenge Closes: Sunday 12/13/15

Good luck!

2

Shouldn’t the last example be:
longest("i don't like pie") -> "don't like p" ?

3

That has multiple spaces.

1 Like
4

I’ll facepalm now. Thanks for clarification.

5

@kmecpp
Given your third example:
longest(“abcdeabcde”) -> “abcde”
“deabc” is also a valid solution, according to your specification. Considering “deabc” and “abcde” have the same length, will either be accepted as a valid solution?

Edit:
If the answer to my above question is true, here is my solution:

Character count (for tiny version): 361

Expanded & nice:

    public static String longestSub(String str) {
        Set<String> subs = new HashSet<>();
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            Set<Character> charSet = new HashSet<>();
            StringBuilder sub = new StringBuilder();
            for (int j = i; j < chars.length; j++) {
                char c = chars[j];
                if (!charSet.contains(c)) {
                    sub.append(c);
                    charSet.add(c);
                } else {
                    break;
                }
            }
            subs.add(sub.toString());
        }

        return subs.stream().sorted((o1, o2) -> o2.length() - o1.length()).findFirst().get();
    }

Expanded:

    public static String l(String s) {
        Set<String> a = new HashSet<>();
        char[] chars = s.toCharArray();
        int l = chars.length;
        for (int i = 0, j; i < l; i++) {
            Set<Character> d = new HashSet<>();
            String g = "";
            for (j = i; j < l; j++) {
                char c = chars[j];
                if (d.contains(c))
                    break;
                else {
                    g = g.concat(String.valueOf(c));
                    d.add(c);
                }
            }
            a.add(g);
        }

        return a.stream().sorted((y, x) -> x.length() - y.length()).findFirst().get();
    }

Tiny:

public static String l(String s){Set<String>a=new HashSet<>();char[]chars=s.toCharArray();int l=chars.length;for(int i=0,j;i<l;i++){Set<Character>d=new HashSet<>();String g="";for(j=i;j<l;j++){char c=chars[j];if(d.contains(c))break;else g=g.concat(String.valueOf(c));d.add(c);}a.add(g);}return a.stream().sorted((y,x)->x.length()-y.length()).findFirst().get();}
6

My entry, 229 characters (223 if you shorten the method name to a single character):

public static String longest(String s){int l=s.length(),i=0,j,k,m=0;for(;i<l;i++){k=0;j=i+1;for(;j<l;j++)if(s.substring(i,j).indexOf(s.charAt(j))>-1)break;m=(k=j-i)>m?k:m;s+=(char)k;}i=s.indexOf(m,l)-l;return s.substring(i,i+m);}

Expanded to be readable:

    static String longest(String s) {
        int l = s.length(), i = 0, j, k, m = 0;
        for (; i < l; i++) {
            k = 0; j = i + 1;
            for (; j < l; j++) 
                if (s.substring(i, j).indexOf(s.charAt(j)) > -1)
                    break;
            m = (k = j - i) > m ? k : m;
            s += (char)k;
        }
        
        i = s.indexOf(m, l) - l;
        return s.substring(i, i + m);
    }

Explanation: iterates through string taking larger substrings until the trailing char is found in the preceding substring, then stops and stores the length of the substring as a char on the end of the source string itself. Keeps track of a “max” value in m and then when finished iterating uses indexOf to find the first instance of (char)m in the string’s tail (the storage area) and returns the substring matching that index + the known max length.

There’s a shorter version of this algorithm which uses regex to the same thing but I personally dislike the “you’re allowed to use imports” rule because it makes the challenge kind of pointless.

7

Note: The forum is auto-replacing \1 in the pattern string with `, so you should make the opposite adjustment to compile.

163 characters:

public static String l(String s){String r="",t;int l=s.length(),i=0,j;for(;i++<l;)for(j=l;j>=i;)if(!(t=s.substring(j-i,j--)).matches(".*(.).*\\1.*"))r=t;return r;}

Longified:

public static String longest(String s) {
    String longest = "";
    for (int i = 1; i <= s.length(); i++) {
        for (int j = s.length(); j >= i; j--) {
            String substring = s.substring(j - i, j);
            if (!substring.matches(".*(.).*\\1.*"))
                longest = substring;
        }
    }
    return longest;
}

The method enumerates all substrings of s (except the ones with length 0) and returns the longest one which does not have a repeated character determined using matches. The outer loop chooses the length of the substring starting with the shortest. The inner loop picks a substring among those with the specified length (in particular, it chooses the second argument to be passed to substring). For example, longest("abcde") would start with substrings of length 1, of which there are 5 (“a”, “b”, “c”, “d”, “e”), and then with substrings of length 2, of which there are 4 (“ab”, “bc”, “cd”, “de”), and then with substrings of length 3, of which there are 3 (“abc”, “bcd”, “cde”), etc.

Below is another one that does the search backwards, starting with the longest substrings and working its way toward the shortest. The first substring encountered that does not have a repeated character is returned. The previous version is shorter because the first return statement is replaced by a shorter assignment statement.

165 characters:

public static String l(String s){String t;int l=s.length(),i=l,j;for(;i>0;i--)for(j=l;j>=i;)if(!(t=s.substring(j-i,j--)).matches(".*(.).*\\1.*"))return t;return "";}

Longified:

public static String longest(String s) {
    for (int i = s.length(); i > 0; i--) {
        for (int j = s.length(); j >= i; j--) {
            String t = s.substring(j - i, j);
            if (!t.matches(".*(.).*\\1.*"))
                return t;
        }
    }
    return "";
}

I’m not too familiar with regexes, but I bet there’s a shorter and fancier way to do this with java.util.regex, possibly without loops.

11

One of the downsides of using an indentation-sensitive language is, well, whitespace.

Here’s my answer in Python, currently 183 characters:

def l(w):
 i,j,x,m=0,0,'',''
 while i<len(w)-1:
  for s in w[i:]:
   if s in x:
    m=x if len(x)>len(m) else m
    x=''
    break
   else:
    x+=s
  i+=1
  j=i
 return m

i is where the substring starts, j is the absolute index of the current symbol to be evaluated, x is the current substring and m is the longest substring. The function iterates over the word until it ends or it finds a duplicate. It then checks to see whether the current substring is longer than the previous longest, and changes it if so. Start index is incremented and substring index is reset. This is repeated for the entire word, then the longest substring is returned.

Edit: Whoops. Apparently it doesn’t work if the string contains only one or two different characters. I’ll have to take a look at that in the morning :stuck_out_tongue:

12

Pfft! You people are shameful! Where are my previous winners? :stuck_out_tongue:

158 characters:

public static String $(String s){String l=s;for(int i=0,j=0;i<=s.length();i++){String t=s.substring(j,i);if(t.matches(".*(.).*\\1.*"))j++;else l=t;}return l;}

Remember to replace the backtick in the regex with \1. It works the similarly to the way you would scan a String with your eyes.

I’ll be posting the next challenge in a bit