Tukukkk

Problem Statement : Given a string of lowercase alphabets, count all possible substrings (not necessarily distinct) that has exactly k distinct characters. Example:

Input: abc, k = 2 Output: 2 Possible substrings are {"ab", "bc"}

I have written the solution with a two pointer approach. I am not sure how to calculate the time complexity of the program?

According to me complexity should be O(n*k)

public static void main(String args)

    {

    String s = "abacuusttlvbnc";

    int k=3;

    char sArr = s.toCharArray();

    int strLen = sArr.length;

    Set<Character> set = new LinkedHashSet<Character>();

    int l=0;

    int r=0;



    while(l<=strLen-k){  // will run (arrayLength - k) times

        for(int i=0;i<k;i++){   // will run k times for every while iteration

            set.add(sArr[l]);

            l++;

        }

        if(set.size()==k){

            System.out.println("substring : " + set);

        }

        set.clear(); // O(k) for every while iteration

        r++;

        l= r;

     }

  }

}

Output :

substring : [b, a, c]

substring : [a, c, u]

substring : [u, s, t]

substring : [t, l, v]

substring : [l, v, b]

substring : [v, b, n]

substring : [b, n, c]

Consider

public static void findSubstringsWithKDistinctCharacters(String s, int k) {

    char letters = s.toCharArray();



    for (int i = 0, n = letters.length - k; i <= n; i++) {

        Set<Character> uniques = new LinkedHashSet<Character>();



        for (int j = i, m = i + k; j < m; j++) {

            uniques.add(letters[j]);

        }



        if (uniques.size() == k) {

            System.out.println("substring : " + uniques);

        }

    }

}

This is a simpler version of what you wrote. It gets rid of your r variable entirely, as it is unnecessary.

I also changed the names of sArr and set to things that I find more descriptive.

I moved the code into its own method so that it can be called multiple times.

There are two reasons to move the declaration of uniques into the loop. One, this is less code. Two, if you changed this code to produce a list of results rather than print the results, the other version doesn't work. You'd have multiple copies of whatever the last set was rather than unique copies. I'd only use the clear version if I knew that performance of this method was a bottleneck.

Bug

Unfortunately, both this version and your original do not match the linked problem statement:

Input: aba, k = 2

Output: 3

Possible substrings are {"ab", "ba", "aba"}

Input: aa, k = 1

Output: 3

Possible substrings are {"a", "a", "aa"}

They only find two solutions for each of these, as they stop counting once there are k characters (distinct or not) in the substring. They should keep going until they've verified that the next character isn't a duplicate of a character already in the substring.

Complexity

Calling the time complexity $mathcal{O}(ncdot k)$ is reasonable. It's slightly more accurate to say that it is $mathcal{O}(ncdot k - k^2)$, but $k$ is never larger than $n$ so it's reasonable to view this as $mathcal{O}(ncdot k)$. Note that if you fix the algorithm, it would be $mathcal{O}(n^2)$, as the worst case is an input of all the same character. That gives substrings up to length $n$ where this is limited to length $k$.

I wrote a little js function given below. The code posted in the question is missing substrings. The string "abacuusttlvbnc" given in the post have possible substrings ["abc", "bac", "acu", "cus", "ust", "stl", "tlv", "lvb", "vbn"]

distinctSubStrings = function(inputStr, subStrLength, returnUniqueList){

        var uniques      = {};

        var uniqueList   = {}; 

        for(var i = 0; i < inputStr.length - subStrLength + 1; i++){

            for(var j = i; Object.keys(uniques).length < subStrLength && j < inputStr.length - 1;j++){

                uniques[inputStr[j]] = '';  

            }

            if(Object.keys(uniques).length === subStrLength){

                uniqueList[Object.keys(uniques).join('')] = '';

            }

            uniques = {};

        }

        return Object.keys(uniqueList);

    }

Usage

console.log(distinctSubStrings("abacuusttlvbnc",3)); 

Complexity $O(n times m)$ Where n is string length and m is the substring length