Question

How to count the number of substrings with exactly k distinct characters in Java

Answer 1

import java.util.Set;
import java.util.HashSet;

public class MyClass {
    public static int CountSubstringWithKDistinctChars(String s, int k) {
        int count = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            String tmp = "" + ch;
            Set<Character> set = new HashSet<Character>();
            set.add(ch);
    
            for (int j = i + 1; j < s.length(); j++) {
                char next_ch = s.charAt(j);
                set.add(next_ch);
                tmp += next_ch;
                if (tmp.length() >= k && set.size() == k) {
                    count++;
                }
            }
        }
        return count;
        
    }
    public static void main(String args[]) {
        String str = "characters";
        int k = 4;
    
        System.out.print("Number of substrings with exactly k distinct characters = ");
        System.out.print(CountSubstringWithKDistinctChars(str, k));
    }
}





/*
run:

Number of substrings with exactly k distinct characters = 9

*/

 

70+ SQL courses for beginners and professionals