Given an integer k and a string s, find the length of the longest substring that contains at most k distinct characters

Question

Given an integer k and a string s, find the length of the longest substring that contains at most k distinct characters.

For example, given s = "abcba" and k = 2, the longest substring with k distinct characters is "bcb".

I found few solutions online like. I felt they were bit too complex. I have tried to simply the solution. But it still lacks readability. How can i further improve?

public class DailyCodingProblem13 {
    public static void main(String args[]) {
        String s = "abcba";
        int k = 2;
        int result = solution(s, k);
        System.out.println(result);

        s = "aabacbebebe";
        k = 2;
        result = solution(s, k);
        System.out.println(result);

        s = "aabbcc";
        k = 3;
        result = solution(s, k);
        System.out.println(result);
    }

    static int solution(String s, int k) {
        int n = s.length();
        int max = 0;
        String maxLengthString = null;
        if (n == 0 || k == 0) {
            return max;
        } else {
            StringBuilder window = new StringBuilder();
            Set<Character> set = new HashSet<>();
            for (int i = 0; i < n; i++) {
                Character ch = s.charAt(i);
                // If
                if (set.size() == k && !set.contains(ch)) {
                    // Fetch the last index of the first character at window. Discard the string
                    // before the last index.
                    window = new StringBuilder(
                            window.substring(window.lastIndexOf(Character.toString(window.charAt(0))) + 1));
                    set.clear();
                    for (int j = 0; j < window.length(); j++) {
                        set.add(window.charAt(j));
                    }
                }
                set.add(ch);
                window.append(ch);
                if (window.length() > max) {
                    max = window.length();
                    maxLengthString = window.toString();
                }
            }
        }
        System.out.println("String with max length is " + maxLengthString.toString());
        return max;
    }

}

Note: This is my huumble effort to create a opensource project with best solutions for leetcode problems. This is not for increasing my score in any coding challenges.

Link to my project.

Answer 1

• Necessary imports are missing.

• The prefix is discarded too aggressively. In a string abaacccc the entire abaa is discarded, and the result becomes 4 instead of 6.

• Representing window as a StringBuilder seems excessive. A pair of indices into the original string is enough.

Answer 2

You've taken away a little bit of readability by creating a variable 'n' for the Strings length.

Either name it sLength, or better yet just use s.length().

This comment does not add any value: // If

You don't need the variable 'max', since it's just a reference to maxLengthString.length(). (Personally I'd return the longest String. But maybe the challenge said otherwise).

You don't need to toString() maxLengthString, since it's already a String.

Instead of using a main method, you could have Unit Tests.

Lastly Eclipse gives me a warning about array brackets being at an illegal position in your Main method. It should be main(String[] args) instead of main(String args[])

@Test
public void test()
{
    String s = "abcba";
    int k = 2;
    assertEquals(3, solution(s, k));

    s = "aabacbebebe";
    k = 2;
    assertEquals(6, solution(s, k));

    s = "aabbcc";
    k = 3;
    assertEquals(6, solution(s, k));

    s = "";
    k = 3;
    assertEquals(0, solution(s, k));
}

static int solution(String s, int k) 
{
    String maxLengthString = "";

    if (s.length() != 0 && k != 0) 
    {
        StringBuilder window = new StringBuilder();
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) 
        {
            char ch = s.charAt(i);
            if (set.size() == k && !set.contains(ch)) 
            {
                // Fetch the last index of the first character at window. Discard the string
                // before the last index.
                window = new StringBuilder(
                        window.substring(window.lastIndexOf(Character.toString(window.charAt(0))) + 1));
                set.clear();
                for (int j = 0; j < window.length(); j++) 
                {
                    set.add(window.charAt(j));
                }
            }
            set.add(ch);
            window.append(ch);
            if (window.length() > maxLengthString.length()) 
            {
                maxLengthString = window.toString();
            }
        }
    }

    System.out.println("String with max length is " + maxLengthString.toString());
    return maxLengthString.length();
}