DEV Community

Aniket Vaishnav
Aniket Vaishnav

Posted on

Substring of length k with k-1 distinct elements

Problem Statement

Given a String S consisting only lowercase alphabets and an integer K. Find the count of all substrings of length K which have exactly K-1 distinct characters.

Link to problem statement:: https://practice.geeksforgeeks.org/problems/substrings-of-length-k-with-k-1-distinct-elements/1

Example 1:

Input:
S = "abcc"
K = 2
Output:
1
Explanation:
Possible substrings of length K = 2 are
ab : 2 distinct characters
bc : 2 distinct characters
cc : 1 distinct character
Only one valid substring exists {"cc"}.
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input:
S = "aabab"
K = 3
Output :
3
Explanation:
Possible substrings of length K = 3 are
aab : 2 distinct characters
aba : 2 distinct characters
bab : 2 distinct characters.
All of these Substrings are a possible answer,
so the count is 3.
Enter fullscreen mode Exit fullscreen mode

Expected Time Complexity: O(|S|)

Expected Auxiliary Space: O(1)

Solution

The problem could be approached with help of two pointers as the length of the expected string is constant K. So the window between the two pointers let's say left(l) and right(*r) is the same and just needs to slide this window one by one character.
The sliding will encounter the elimination of the previous character and the inclusion of a new character. According to this, character map should be updated. The character map is the map maintaining, characters with their frequency in the window.

class Solution {
    static int countOfSubstrings(String S, int k) {
        char[] s = S.toCharArray();
        int l = 0;
        int r = 0;
        int cnt = 0;
        HashMap<Character, Integer> map = new HashMap<>();

        // initial map setting for window
        for(; r < k; r++) {
            map.put(s[r], map.getOrDefault(s[r], 0) + 1);
        }

        int res = map.size() == k - 1? 1 : 0;

        // gradually incrementing window
        for (; r < s.length; r++, l++) {
            // adding the character
            map.put(s[r], map.getOrDefault(s[r], 0) + 1);

            // removing character
            if( map.get(s[l]) == 1 ) {
                // remove character 
                // if it was the only character
                // into the window
                map.remove(s[l]);
            } else {
                map.put(s[l], map.get(s[l]) - 1);
            }
            if(map.size() == k-1) res++;
        }

        return res;
    }
}
Enter fullscreen mode Exit fullscreen mode

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay