Imports System
Imports System.Collections.Generic
Module SubstringWithKDistinct
' Function to get all substrings with exactly k distinct characters
Function GetSubstringsWithKDistinct(s As String, k As Integer) As List(Of String)
Dim listOfSubstrings As New List(Of String)()
Dim n As Integer = s.Length
' Iterate over all possible starting points of substrings
For i As Integer = 0 To n - 1
Dim freqMap As New Dictionary(Of Char, Integer)() ' Map to count character frequencies
Dim distinctCount As Integer = 0 ' Counter for distinct characters in current substring
' Extend the substring from position i to j
For j As Integer = i To n - 1
Dim ch As Char = s(j) ' Current character
' If character is new to the substring, increment distinct count
If Not freqMap.ContainsKey(ch) Then
distinctCount += 1
freqMap(ch) = 1
Else
freqMap(ch) += 1
End If
' If we have exactly k distinct characters, store the substring
If distinctCount = k Then
listOfSubstrings.Add(s.Substring(i, j - i + 1))
ElseIf distinctCount > k Then
Exit For ' Stop exploring this substring
End If
Next
Next
Return listOfSubstrings
End Function
Sub Main()
Dim str As String = "characters"
Dim k As Integer = 4
Dim substrings As List(Of String) = GetSubstringsWithKDistinct(str, k)
Console.WriteLine($"Number of substrings with exactly k distinct characters = {substrings.Count}")
Console.WriteLine()
Console.WriteLine($"Substrings with exactly {k} distinct characters in '{str}':")
For Each subStr As String In substrings
Console.WriteLine(subStr)
Next
End Sub
End Module
' run:
'
' Number of substrings with exactly k distinct characters = 9
'
' Substrings with exactly 4 distinct characters in 'characters':
' char
' chara
' charac
' harac
' aract
' ract
' acte
' cter
' ters
'
' run:
'
' 37
'
