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