3
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ I'd say O(n*k) is a reasonable representation. Did you try using subString rather than putting in the little loop? Depending on subString's implementation, it may reduce the complexity of your program to O(n) \$\endgroup\$ – Maybe_Factor Aug 5 '16 at 0:38
  • \$\begingroup\$ subString sounds good but every time subString returns a new String that would add to the space complexity of the program. Even the StringBuilder subString method returns a new String. What do you think? \$\endgroup\$ – underdog Aug 5 '16 at 15:33
  • \$\begingroup\$ If memory is an issue then using subString might not be a good idea. I hadn't considered the creation of new Strings... that could make any time savings moot anyway. \$\endgroup\$ – Maybe_Factor Aug 8 '16 at 1:51
4
\$\begingroup\$

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}(n\cdot k)\$ is reasonable. It's slightly more accurate to say that it is \$\mathcal{O}(n\cdot k - k^2)\$, but \$k\$ is never larger than \$n\$ so it's reasonable to view this as \$\mathcal{O}(n\cdot 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\$.

\$\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.