[Week Fourteen] Programming Contest - Shortest Substring

General Discussion Off Topic
1

Welcome back to 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

NOTE: I have added a new rule to the book which is that submissions with compile time errors OR WARNINGS will not be accepted.

This week’s challenge is to write a method that takes in two Strings and returns the length of the shortest substring of the first string that contains all the characters of the second, and -1 if none exists. So your method take in exactly two Strings and returns one integer.

Your method should be case insensitive.

Examples:

shortest(“Hello”, “hell”) -> 4
(substring: “hell”)

shortest(“SpongePowered”, “power”) -> 5
(substring: “power”)

shortest(“SpongePowered”, “PWND”) -> 10
(substring: “ngepowered”)

shortest(“I once ate a pickle lol”, “PILL”) -> 8
(substring: “pickle l”)

shortest(“Did the quick brown fox jump over the lazy dog?!”, “OOOO”) -> 29
(substring: “own fox jump over the lazy do”)

shortest(“i’m really uncreative when it comes to thinking of examples”, “correct”) -> 28
(substring: “really uncreative when it co”)

Also, if you like these weekly programming problems, please make some suggestions for the contest or specific challenges (in the main thread)! This takes time out of my Sunday and its not always fun! Using suggested challenges makes it a lot faster and easier for me.

Imports are allowed for this challenge!

Challenge Closes: Sunday 2/7/16

Good luck!

2

OR WARNINGS

But warnings depend on IDE, project settings, global options, etc.

3

True, would you agree with default Eclipse settings to determine warnings?

What does everyone else think?

4

I don’t think most of us use Eclipse.

5

Condensed 223 characters:

public static int s(String c,String r){String f="";boolean m=false;for(String l:c.split("")){if(r.isEmpty())break;if(r.contains(l)){m=true;r=r.replaceFirst(Pattern.quote(l),"");}if(m)f+=l;}return r.isEmpty()?f.length():-1;}

Readable 587 characters:

    public static int shortestLength(String check, String require) {
        String returned = "";
        boolean firstMatch = false;

        for (String current : check.split("")) {
            if (require.isEmpty()) {
                break;
            }

            if (require.contains(current)) {
                firstMatch = true;
                require = require.replaceFirst(Pattern.quote(current), "");
            }
            
            if (firstMatch) {
                returned += current;
            }
        }

        return require.isEmpty() ? returned.length() : -1;
    }
6

that fails in cases like (“aab”,“ab”) -> 2 where the first character in the first string that is in the second string is not in the shortest substring.

7

This should return 30, not 29.

8

Extra “s”. Fixed it

9

236 characters

public static int s(String c,String r){for(int l=c.length(),i=0,j;i++<l;)for(j=i;j<=l;)if(Stream.of(r.toLowerCase().split("")).allMatch(new Vector(Arrays.asList(c.toLowerCase().substring(j-i,j++).split("")))::remove))return i;return-1;}

Unminified:

public static int s(String a, String b) {
    for (int l = a.length(), substringLength = 0, endIndex; substringLength++ < l; )
        for (endIndex = substringLength; endIndex <= l; )
            if (Stream.of(b.toLowerCase().split(""))
                    .allMatch(new Vector(Arrays.asList(a.toLowerCase().substring(endIndex - substringLength, endIndex++).split("")))::remove))
                return substringLength;
    return -1;
}

Java’s standard library could really use a Multiset. That would have made this challenge quite a bit easier.

10

Congratulations to @jus1in for winning week fourteen!

The next challenge should be up shortly.