Program in C++

Problem Statement :

Given a string, find the substring with minimum length from it which contains exactly equal no of characters given in a hashmap which contains key as character and values as count of character needed in substring.

Solution:

//substring.cpp

#include "iostream.h"

#include "cstdio"

#include "string.h"

#include "map.h"

using namespace std;

string find_substr(map<char,int> mapcpy,string s)

{

map

<char,int>

mapcopy;

char x;

unsigned int tot_len=0,l=0;

int i=0;

int pos=0;

int minpos=0;
int flag=1;
int min=s.length(); 

//calculating the minimum length of the substring , which is nothing but the sum of value field in the map for each key.

for(x='a'; x<'z'; x++)

{

tot_len += mapcpy[x];

}

//if the length of string entered is less than the minimum length required, there is no use of checking.

if(s.length() < tot_len)

return " ";

//checking index position in outer loop while traversing the string.

while( i < s.length() && s.length()-i >=tot_len )

{

l=tot_len;

mapcopy=mapcpy;

while(s[i]!='\0')

{

//if the value of key s[i] is 0, this means either s[i] is not required to be present //or the required no of its occurence has already occured.

if(mapcopy[s[i]] > 0)

{

mapcopy[s[i]]--;
                        l--;                           //decreasing count of character found in string

} //increasing index

i++;; //decresing min length with each char found

if(l==0 && i-pos+1 < min) //purpose served if l==0

{
                                 flag=0;

minpos=pos; //start index from where min string is found
min=i-pos+1; // min length

}

}

i=++pos; //incrementing index to next position in the string from where it started //earlier.

}
if(flag ==0 )
{

return  s.substr(minpos,min);

}
else
{
return "";
}

}

int main()

{

map

<char,int>

map1;

string s_name;

string output;

//inserting values in the map for certain characters.

map1.insert(pair('a',2));

map1.insert(pair('m',1));

map1.insert(pair('d',1));

map1.insert(pair('g',1));

map1.insert(pair('r',1));

map1.insert(pair('i',1));

//Entering a string in which the substring needs to be found.

cout<<"Enter a string :";

getline(cin,s_name,'\n');

//output gets the first occurence of substring stored.

output = find_substr(map1,s_name);

cout<<"The String is : "<<output;

}

Compiling : g++ -o output substring.cpp

Running output : ./output