1
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$
  • 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.

\$\endgroup\$
2
\$\begingroup\$

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();
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.