Length of the smallest sub-string consisting of maximum distinct characters

Last Updated : 05 Aug, 2024

Given a string of length N, find the length of the smallest sub-string consisting of maximum distinct characters. Note : Our output can have same character.

Examples:

Input : "AABBBCBB"
Output : 5

Input : "AABBBCBBAC"
Output : 3
Explanation : Sub-string -> "BAC"

Input : "GEEKSGEEKSFOR"
Output : 8
Explanation : Sub-string -> "GEEKSFOR"

Method 1 (Brute Force)

We can consider all sub-strings one by one and check for each sub-string both conditions together

sub-string’s distinct characters is equal to maximum distinct characters
sub-string’s length should be minimum.

Implementation:

C++

/* C++ program to find the length of the smallest 
substring consisting of maximum distinct characters */
#include <bits/stdc++.h>
using namespace std;

#define NO_OF_CHARS 256

// Find maximum distinct characters in any string
int max_distinct_char(string str, int n){

    // Initialize all character's count with 0
    int count[NO_OF_CHARS] = {0};
    
    // Increase the count in array if a character
    // is found
    for (int i = 0; i < n;  i++)
        count[str[i]]++;
    
    int max_distinct = 0;
    for (int i = 0; i < NO_OF_CHARS;  i++)
        if (count[i] != 0)      
            max_distinct++;     
    
    return max_distinct;
}

int smallesteSubstr_maxDistictChar(string str){

    int n = str.size();     // size of given string

    // Find maximum distinct characters in any string
    int max_distinct = max_distinct_char(str, n);
    int minl = n;   // result
    
    // Brute force approach to find all substrings
    for (int i=0 ;i<n ;i++){
        for (int j=0; j<n; j++){
            string subs =  str.substr(i,j);
            int subs_lenght = subs.size();
            int sub_distinct_char = max_distinct_char(subs, subs_lenght); 
            
            // We have to check here both conditions together
            // 1. substring's distinct characters is equal
            //    to maximum distinct characters
            // 2. substring's length should be minimum 
            if (subs_lenght < minl && max_distinct == sub_distinct_char){
                minl = subs_lenght;
            }
        }
    }
    return minl;
}

/* Driver program to test above function */
int main()
{
    // Input String
    string str = "AABBBCBB";
    
    int len =  smallesteSubstr_maxDistictChar(str);
    cout << " The length of the smallest substring"
            " consisting of maximum distinct "
            "characters : " << len;
    return 0;
}

Java

/* Java program to find the length of the smallest 
substring consisting of maximum distinct characters */
class GFG {

    final static int NO_OF_CHARS = 256;

// Find maximum distinct characters in any string
    static int max_distinct_char(String str, int n) {

        // Initialize all character's count with 0
        int count[] = new int[NO_OF_CHARS];

        // Increase the count in array if a character
        // is found
        for (int i = 0; i < n; i++) {
            count[str.charAt(i)]++;
        }

        int max_distinct = 0;
        for (int i = 0; i < NO_OF_CHARS; i++) {
            if (count[i] != 0) {
                max_distinct++;
            }
        }

        return max_distinct;
    }

    static int smallesteSubstr_maxDistictChar(String str) {

        int n = str.length();     // size of given string

        // Find maximum distinct characters in any string
        int max_distinct = max_distinct_char(str, n);
        int minl = n;   // result

        // Brute force approach to find all substrings
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                
                String subs = null;
                if(i<j)
                    subs = str.substring(i, j);
                else
                    subs = str.substring(j, i);
                int subs_lenght = subs.length();
                int sub_distinct_char = max_distinct_char(subs, subs_lenght);

                // We have to check here both conditions together
                // 1. substring's distinct characters is equal
                //    to maximum distinct characters
                // 2. substring's length should be minimum 
                if (subs_lenght < minl && max_distinct == sub_distinct_char) {
                    minl = subs_lenght;
                }
            }
        }
        return minl;
    }

    /* Driver program to test above function */
    static public void main(String[] args) {
        // Input String
        String str = "AABBBCBB";

        int len = smallesteSubstr_maxDistictChar(str);
        System.out.println(" The length of the smallest substring"
                + " consisting of maximum distinct "
                + "characters : "+len);
    }
}

// This code is contributed by 29AjayKumar

Python

# Python 3 program to find the length 
# of the smallest substring consisting
# of maximum distinct characters 
NO_OF_CHARS = 256

# Find maximum distinct characters
# in any string
def max_distinct_char(str, n):

    # Initialize all character's
    # count with 0
    count = [0] * NO_OF_CHARS
    
    # Increase the count in array 
    # if a character is found
    for i in range(n):
        count[ord(str[i])] += 1
    
    max_distinct = 0
    for i in range(NO_OF_CHARS):
        if (count[i] != 0):
            max_distinct += 1    
    
    return max_distinct

def smallesteSubstr_maxDistictChar(str):

    n = len(str)     # size of given string

    # Find maximum distinct characters
    # in any string
    max_distinct = max_distinct_char(str, n)
    minl = n     # result
    
    # Brute force approach to
    # find all substrings
    for i in range(n):
        for j in range(n):
            subs = str[i:j]
            subs_lenght = len(subs)
            sub_distinct_char = max_distinct_char(subs, 
                                                  subs_lenght)
            
            # We have to check here both conditions together
            # 1. substring's distinct characters is equal
            # to maximum distinct characters
            # 2. substring's length should be minimum 
            if (subs_lenght < minl and 
                max_distinct == sub_distinct_char):
                minl = subs_lenght

    return minl

# Driver Code
if __name__ == "__main__":
    
    # Input String
    str = "AABBBCBB"
    
    l = smallesteSubstr_maxDistictChar(str);
    print( "The length of the smallest substring",
           "consisting of maximum distinct",
           "characters :", l)

# This code is contributed by ChitraNayal

/* C# program to find the length of the smallest 
substring consisting of maximum distinct characters */
using System;
    
class GFG 
{

    static int NO_OF_CHARS = 256;

    // Find maximum distinct characters in any string
    static int max_distinct_char(String str, int n) 
    {

        // Initialize all character's count with 0
        int []count = new int[NO_OF_CHARS];

        // Increase the count in array if a character
        // is found
        for (int i = 0; i < n; i++) 
        {
            count[str[i]]++;
        }

        int max_distinct = 0;
        for (int i = 0; i < NO_OF_CHARS; i++)
        {
            if (count[i] != 0) 
            {
                max_distinct++;
            }
        }

        return max_distinct;
    }

    static int smallesteSubstr_maxDistictChar(String str)
    {

        int n = str.Length;     // size of given string

        // Find maximum distinct characters in any string
        int max_distinct = max_distinct_char(str, n);
        int minl = n; // result

        // Brute force approach to find all substrings
        for (int i = 0; i < n; i++) 
        {
            for (int j = 0; j < n; j++) 
            {
                
                String subs = null;
                if(i < j)
                    subs = str.Substring(i, str.Length-j);
                else
                    subs = str.Substring(j, str.Length-i);
                int subs_lenght = subs.Length;
                int sub_distinct_char = max_distinct_char(subs, subs_lenght);

                // We have to check here both conditions together
                // 1. substring's distinct characters is equal
                // to maximum distinct characters
                // 2. substring's length should be minimum 
                if (subs_lenght < minl && max_distinct == sub_distinct_char)
                {
                    minl = subs_lenght;
                }
            }
        }
        return minl;
    }

    /* Driver program to test above function */
    static public void Main(String[] args)
    {
        // Input String
        String str = "AABBBCBB";

        int len = smallesteSubstr_maxDistictChar(str);
        Console.WriteLine(" The length of the smallest substring"
                + " consisting of maximum distinct "
                + "characters : "+len);
    }
}

// This code contributed by Rajput-Ji

JavaScript

<script>

// Javascript program to find the length
// of the smallest substring consisting 
// of maximum distinct characters 
let NO_OF_CHARS = 256;

// Find maximum distinct characters
// in any string
function max_distinct_char(str, n)
{
    
    // Initialize all character's 
    // count with 0
    let count = new Array(NO_OF_CHARS);
    for(let i = 0; i < count.length; i++)
    {
        count[i] = 0;
    }

    // Increase the count in array if a
    // character is found
    for(let i = 0; i < n; i++)
    {
        count[str[i].charCodeAt(0)]++;
    }

    let max_distinct = 0;
    for(let i = 0; i < NO_OF_CHARS; i++)
    {
        if (count[i] != 0) 
        {
            max_distinct++;
        }
    }
    return max_distinct;
}

function smallesteSubstr_maxDistictChar(str)
{
    
    // Size of given string
    let n = str.length;    

    // Find maximum distinct characters
    // in any string
    let max_distinct = max_distinct_char(str, n);
    
    // Result
    let minl = n;   

    // Brute force approach to find all
    // substrings
    for(let i = 0; i < n; i++) 
    {
        for(let j = 0; j < n; j++) 
        {
            let subs = null;
            
            if (i < j)
                subs = str.substring(i, j);
            else
                subs = str.substring(j, i);
                
            let subs_lenght = subs.length;
            let sub_distinct_char = max_distinct_char(
                subs, subs_lenght);

            // We have to check here both conditions together
            // 1. substring's distinct characters is equal
            //    to maximum distinct characters
            // 2. substring's length should be minimum 
            if (subs_lenght < minl && 
                max_distinct == sub_distinct_char) 
            {
                minl = subs_lenght;
            }
        }
    }
    return minl;
}

// Driver Code
let str = "AABBBCBB";
let len = smallesteSubstr_maxDistictChar(str);

document.write("The length of the smallest substring" + 
               " consisting of maximum distinct " + 
               "characters : " + len);

// This code is contributed by avanitrachhadiya2155
    
</script>

PHP

<?php
/* PHP program to find the length of the smallest 
substring consisting of maximum distinct characters */

$NO_OF_CHARS=256;

// Find maximum distinct characters in any string
function max_distinct_char($str, $n)
{
    global $NO_OF_CHARS;
    
    // Initialize all character's count with 0
    $count = array_fill(0, $NO_OF_CHARS, 0);
    
    // Increase the count in array if a character
    // is found
    for ($i = 0; $i < $n; $i++)
        $count[ord($str[$i])]++;
    
    $max_distinct = 0;
    for ($i = 0; $i < $NO_OF_CHARS; $i++)
        if ($count[$i] != 0)     
            $max_distinct++;     
    
    return $max_distinct;
}

function smallesteSubstr_maxDistictChar($str)
{

    $n = strlen($str); // size of given string

    // Find maximum distinct characters in any string
    $max_distinct = max_distinct_char($str, $n);
    $minl = $n; // result
    
    // Brute force approach to find all substrings
    for ($i = 0 ; $i < $n ; $i++)
    {
        for ($j = 0; $j < $n; $j++)
        {
            $subs = substr($str, $i, $j);
            $subs_lenght = strlen($subs);
            $sub_distinct_char = max_distinct_char($subs, $subs_lenght); 
            
            // We have to check here both conditions together
            // 1. substring's distinct characters is equal
            // to maximum distinct characters
            // 2. substring's length should be minimum 
            if ($subs_lenght < $minl && 
                $max_distinct == $sub_distinct_char)
            {
                $minl = $subs_lenght;
            }
        }
    }
    return $minl;
}

/* Driver code */

    // Input String
    $str = "AABBBCBB";
    
    $len = smallesteSubstr_maxDistictChar($str);
    echo " The length of the smallest substring"
            ." consisting of maximum distinct characters : ".$len;

// This code is contributed by mits
?>

Output

 The length of the smallest substring consisting of maximum distinct characters : 5

Time Complexity : O(n³)
Auxiliary Space: O(n)

Method 2 (Efficient)

Count all distinct characters in given string.
Maintain a window of characters. Whenever the window contains all characters of given string, we shrink the window from left side to remove extra characters and then compare its length with smallest window found so far.

Implementation:

C++

/* C++ program to find the length of the smallest
substring consisting of maximum distinct characters */
#include <bits/stdc++.h>
using namespace std;

// A function which accepts a string and returns length of
// the smallest substring consisting of maximum distinct
// characters
int smallesteSubstr_maxDistictChar(string str)
{
    // to get the number of unique characters
    unordered_set<char> st;
    // traverse the string once and store the  characters
    for (int i = 0; i < str.length(); i++)
        st.insert(str[i]);
    // number of unique characters
    int unique = st.size();
      unordered_map<char, int> mp;
    // to store the result
    int res = INT_MAX;
    int j = 0; // starting index of window
    for (int i = 0; i < str.length(); i++) {
        // add the current character in window
        mp[str[i]]++;
        // while number of distinct elements in the map is
        // equal to unique characters and starting element
        // of the window has frequency more than one we keep
        // reducing its frequency and increasing the
        // starting point of the window 
        while (mp.size() == unique && mp[str[j]] > 1) {
            mp[str[j]]--;
            j++;
        }
        // if size of map is equal to unique elements update
        // the result
        if (mp.size() == unique)
            res = min(i - j + 1, res);
    }
    return res;
}

/* Driver program to test above function */
int main()
{
    // Input String
    string str = "AABBBCBB";

    int len = smallesteSubstr_maxDistictChar(str);
    cout << " The length of the smallest substring"
            " consisting of maximum distinct "
            "characters : "
         << len;
    return 0;
}

// This code was contributed by Abhijeet Kumar(abhijeet19403)

Java

/* Java program to find the length of the smallest
substring consisting of maximum distinct characters */
import java.util.*;

class GFG {
  
    static final int MAX_CHARS = 256;
    // Find maximum distinct characters in any string
    static int max_distinct_char(String str, int n)
    {
        // Initialize all character's count with 0
        int count[] = new int[MAX_CHARS];
        int max_distinct = 0;
        // Increase the count of max_distinct if a character
        // is found to have a frequency of 1
        for (int i = 0; i < n; i++) {
            count[str.charAt(i)]++;
            if (count[str.charAt(i)] == 1)
                max_distinct++;
        }
        return max_distinct;
    }
    // A function which accepts a string and returns length
    // of the smallest substring consisting of maximum distinct
    // characters
    static int smallestSubstr_maxDistictChar(String str)
    {
        int n = str.length();
        // number of unique characters
        int unique = max_distinct_char(str, n);
        // to store the result
          int res = Integer.MAX_VALUE;
        Map<Character, Integer> mp
            = new HashMap<Character, Integer>();
        
        int j = 0; // starting index of window
        for (int i = 0; i < str.length(); i++) {
            // add the current character in window
            char c = str.charAt(i);
            if (mp.containsKey(c))
                mp.put(c, mp.get(c) + 1);
            else
                mp.put(c, 1);
            // while no. of distinct elements in the map is
            // equal to unique characters and starting
            // element of the window has frequency more than
            // one we keep reducing its frequency and
            // increasing the starting point of the window
          
            while (mp.size() == unique
                   && mp.get(str.charAt(j)) > 1) {
                mp.put(str.charAt(j),
                       (mp.get(str.charAt(j)) - 1));
                j++;
            }
            // if size of map is equal to unique elements
            // update the result
            if (mp.size() == unique)
                res = Math.min(i - j + 1, res);
        }
        return res;
    }

    /* Driver program to test above function */
    static public void main(String[] args)
    {
        // Input String
        String str = "AABBBCBB";

        int len = smallestSubstr_maxDistictChar(str);
        System.out.println(
            " The length of the smallest substring"
            + " consisting of maximum distinct "
            + "characters : " + len);
    }
}

// This code is contributed by Abhijeet Kumar(abhijeet19403)

Python

import sys
import math

class GFG :
    MAX_CHARS = 256
    
    # Find maximum distinct characters in any string
    @staticmethod
    def  max_distinct_char( str,  n) :
        # Initialize all character's count with 0
        count = [0] * (GFG.MAX_CHARS)
        max_distinct = 0
        
        # Increase the count of max_distinct if a character
        # is found to have a frequency of 1
        i = 0
        while (i < n) :
            count[ord(str[i])] += 1
            if (count[ord(str[i])] == 1) :
                max_distinct += 1
            i += 1
        return max_distinct
      
    # A function which accepts a string and returns length
    # of the smallest substring consisting of maximum distinct
    # characters
    @staticmethod
    def  smallestSubstr_maxDistictChar( str) :
        n = len(str)
        
        # number of unique characters
        unique = GFG.max_distinct_char(str, n)
        
        # to store the result
        res = sys.maxsize
        mp =  dict()
        j = 0
        
        # starting index of window
        i = 0
        while (i < len(str)) :
            # add the current character in window
            c = str[i]
            if ((c in mp.keys())) :
                mp[c] = mp.get(c) + 1
            else :
                mp[c] = 1
                
            # while no. of distinct elements in the map is
            # equal to unique characters and starting
            # element of the window has frequency more than
            # one we keep reducing its frequency and
            # increasing the starting point of the window
            while (len(mp) == unique and mp.get(str[j]) > 1) :
                mp[str[j]] = (mp.get(str[j]) - 1)
                j += 1
                
            # if size of map is equal to unique elements
            # update the result
            if (len(mp) == unique) :
                res = min(i - j + 1,res)
            i += 1
        return res
      
    # Driver program to test above function
    @staticmethod
    def main( args) :
      
        # Input String
        st = "AABBBCBB"
        len = str(GFG.smallestSubstr_maxDistictChar(st))
        print(" The length of the smallest substring" + " consisting of maximum distinct " + "characters : " + len)
    
if __name__=="__main__":
    GFG.main([])
    
    # This code is contributed by adityaburujwale.

/* C# program to find the length of the smallest 
substring consisting of maximum distinct characters */
using System;
using System.Collections.Generic;

class GFG 
{
    static int MAX_CHARS = 256;

    // Find maximum distinct characters in any string
    static int max_distinct_char(String str, int n) 
    {
          // Initialize all character's count with 0
        int[] count = new int[MAX_CHARS];
        int max_distinct = 0;
        // Increase the count of max_distinct if a character
        // is found to have a frequency of 1
        for (int i = 0; i < n; i++) {
            count[str[i]]++;
            if (count[str[i]] == 1)
                max_distinct++;
        }
        return max_distinct;
    }

    static int smallestSubstr_maxDistictChar(String str)
    {
        int n = str.Length;
        // number of unique characters
        int unique = max_distinct_char(str, n);
        // to store the result
          int res = int.MaxValue;
      
        Dictionary<char, int> mp  = new Dictionary<char, int>();
        int j = 0; // starting index of window
      
        for (int i = 0; i < n; i++) {
            // add the current character in window
            if (mp.ContainsKey(str[i]))
                mp[str[i]]++;
            else
                mp.Add(str[i], 1);
            
            // while no. of distinct elements in the map is
            // equal to unique characters and starting
            // element of the window has frequency more than
            // one we keep reducing its frequency and
            // increasing the starting point of the window
            while (mp.Count == unique && mp[str[j]] > 1) 
            {
                mp[str[j]]--;
                j++;
            }
            // if size of map is equal to unique elements
            // update the result
            if (mp.Count == unique)
                res = Math.Min(i - j + 1, res);
        }
        return res;
      
    }

    /* Driver program to test above function */
    static public void Main(String[] args)
    {
        // Input String
        String str = "AABBBCBB";

        int len = smallestSubstr_maxDistictChar(str);
        Console.WriteLine(" The length of the smallest substring"
                + " consisting of maximum distinct "
                + "characters : "+len);
    }
}

// This code contributed by Abhijeet Kumar(abhijeet19403)

JavaScript

     var MAX_CHARS = 256;
     
    // Find maximum distinct characters in any string
    function max_distinct_char(str, n)
    {
    
        // Initialize all character's count with 0
        var count = Array(MAX_CHARS).fill(0);
        var max_distinct = 0;
        
        // Increase the count of max_distinct if a character
        // is found to have a frequency of 1
        var i=0;
        for (i; i < n; i++)
        {
            count[str.charAt(i).charCodeAt(0)]++;
            if (count[str.charAt(i).charCodeAt(0)] == 1)
            {
                max_distinct++;
            }
        }
        return max_distinct;
    }
    
    // A function which accepts a string and returns length
    // of the smallest substring consisting of maximum distinct
    // characters
    function smallestSubstr_maxDistictChar(str)
    {
        var n = str.length;
        
        // number of unique characters
        var unique = max_distinct_char(str, n);
        
        // to store the result
        var res = Number.MAX_VALUE;
        var mp = new Map();
        var j = 0;
        
        // starting index of window
        var i=0;
        for (i; i < str.length; i++)
        {
        
            // add the current character in window
            var c = str.charAt(i);
            if (mp.has(c))
            {
                mp.set(c,mp.get(c) + 1);
            }
            else 
            {
                mp.set(c,1);
            }
            
            // while no. of distinct elements in the map is
            // equal to unique characters and starting
            // element of the window has frequency more than
            // one we keep reducing its frequency and
            // increasing the starting point of the window
            while (mp.size == unique && mp.get(str.charAt(j)) > 1)
            {
                mp.set(str.charAt(j),(mp.get(str.charAt(j)) - 1));
                j++;
            }
            
            // if size of map is equal to unique elements
            // update the result
            if (mp.size == unique)
            {
                res = Math.min(i - j + 1,res);
            }
        }
        return res;
    }
    
    // Driver program to test above function
    
        // Input String
        var str = "AABBBCBB";
        var len = smallestSubstr_maxDistictChar(str);
        console.log(" The length of the smallest substring" + " consisting of maximum distinct " + "characters : " + len);

// This code is contributed by sourabhdalal0001.

Output

 The length of the smallest substring consisting of maximum distinct characters : 5

Time Complexity: O(n), As we doing linear operations on string.
Auxiliary Space: O(n), As constant extra space is used. The size of set and map can only go upto a maximum size of 256 which is a constant thus the extra space used is also constant.

Please refer Smallest window that contains all characters of string itself more details.
Asked In : DailyHunt