Find the longest substring with k unique characters in a given string - GeeksforGeeks

Find the longest substring with k unique characters in a given string - GeeksforGeeks
http://massivealgorithms.blogspot.com/2014/12/leetcode-longest-substring-with-at-most.html
Given a string you need to print longest possible substring that has exactly M unique characters. If there are more than one substring of longest possible length, then print any one of them.

The problem can be solved in O(n). Idea is to maintain a window and add elements to the window till it contains less or equal k, update our result if required while doing so. If unique elements exceeds than required in window, start removing the elements from left side.

// This function calculates number of unique characters

// using a associative array count[]. Returns true if

// no. of characters are less than required else returns

// false.

bool isValid(int count[], int k)

{

    int val = 0;

    for (int i=0; i<MAX_CHARS; i++)

        if (count[i] > 0)

            val++;

 

    // Return true if k is greater than or equal to val

    return (k >= val);

}

 

// Finds the maximum substring with exactly k unique chars

void kUniques(string s, int k)

{

    int u = 0; // number of unique characters

    int n = s.length();

 

    // Associative array to store the count of characters

    int count[MAX_CHARS];

    memset(count, 0, sizeof(count));

 

    // Traverse the string, Fills the associative array

    // count[] and count number of unique characters

    for (int i=0; i<n; i++)

    {

        if (count[s[i]-'a']==0)

            u++;

        count[s[i]-'a']++;

    }

 

    // If there are not enough unique characters, show

    // an error message. exit early

    if (u < k)

    {

        cout << "Not enough unique characters";

        return;

    }

 

    // Otherwise take a window with first element in it.

    // start and end variables.

    int curr_start = 0, curr_end = 0;

 

    // Also initialize values for result longest window

    int max_window_size = 1, max_window_start = 0;

 

    // Initialize associative array count[] with zero

    memset(count, 0, sizeof(count));

 

    count[s[0]-'a']++;  // put the first character

 

    // Start from the second character and add

    // characters in window according to above

    // explanation

    for (int i=1; i<n; i++)

    {

        // Add the character 's[i]' to current window

        count[s[i]-'a']++;

        curr_end++;

 

        // If there are more than k unique characters in

        // current window, remove from left side

        while (!isValid(count, k))

        {

            count[s[curr_start]-'a']--;

            curr_start++;

        }

 

        // Update the max window size if required

        if (curr_end-curr_start+1 > max_window_size)

        {

            max_window_size = curr_end-curr_start+1;

            max_window_start = curr_start;

        }

    }

 

    cout << "Max sustring is : "

         << s.substr(max_window_start, max_window_size)

         << " with length " << max_window_size << endl;

}

Also check: http://massivealgorithms.blogspot.com/2014/12/leetcode-longest-substring-with-at-most.html

Read full article from Find the longest substring with k unique characters in a given string - GeeksforGeeks