Method to the lowest letter (in alphabetical order) in a string

Question

I am trying to write a simple method that takes a String and returns the smallest letter of that String. For example, given the String "basic", "a" should be returned.

Here's the code that I've come up with. Currently I am getting an OutOfMemoryError. You will also notice that I've attempted to use recursion, but I am also open to suggestions that do not use recursion.

public static String smallestLetter(String str) {
        if (str.length() == 1)
            return str.substring(0);
        else if (str.charAt(0) < str.charAt(1))
            return smallestLetter(str.substring(0) + str.substring(2,str.length()));
        else
            return smallestLetter(str.substring(1,str.length()));
}

Please let me know where I'm going wrong and what I can do to fix it. Thanks!

Answer 1

The problem is this line:

        return smallestLetter(str.substring(0) + str.substring(2,str.length()));

str.substring(0) is actually the entire string; so in this line, the method re-calls itself with a string that's almost twice as big as the original. Just a few method-calls in, you can already have a massive string that's bigger than you can allocate.

The minimal fix is:

        return smallestLetter(str.charAt(0) + str.substring(2,str.length()));

but a better fix is to use iteration rather than recursion:

public static String smallestLetter(String str) {
    char ret = str.charAt(0);
    for (int i = 1; i < str.length(); ++i)
        if (str.charAt(i) < ret)
            ret = str.charAt(i);
    return String.valueOf(ret);
}

Edited to add: Note that, as Alexey Malev points out below, this will raise an exception if str is the empty string (""). In addition, it does not do any filtering to specifically identify letters; rather, it will return the least character in the string, whether or not that's a letter.

Answer 2

I think you code goes too deep into recursion and at some moment the heap memory is over.

If we assume that you need to find only Latin letters, I'd do it like that:

public static String smallestLetter(String str) {
    for (Character ch = 'a'; ch <= 'z'; ++ch) {
        if (str.contains(String.valueOf(ch))) {
            return String.valueOf(ch);
        }
    }
    return "No characters in the string :(";
}    

Answer 3

Try this:

char min = s.charAt(0);
for (int i = 0; i < s.length(); i++)
    if (Character.isLetter(s.charAt(i)) && s.charAt(i) < min)
        min = s.charAt(i);
return min;