Length of smallest substring of a given string which contains another string as subsequence | C ++ program to implement the above approach ; Function to find the length of smallest substring of a having string b as a subsequence ; Stores the characters present in string b ; Find index of characters of a that are also present in string b ; If character is present in string b ; Store the index of character ; Flag is used to check if substring is possible ; Assume that substring is possible ; Stores first and last indices of the substring respectively ; For first character of string b ; If the first character of b is not present in a ; If the first character of b is present in a ; Remove the index from map ; Update indices of the substring ; For the remaining characters of b ; If index possible for current character ; If no index is possible ; If no more substring is possible ; Update the minimum length of substring ; Return the result ; Driver Code ; Given two string
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minLength ( string a , string b ) { map < char , int > Char ; for ( int i = 0 ; i < b . length ( ) ; i ++ ) { Char [ b [ i ] ] ++ ; } map < char , vector < int > > CharacterIndex ; for ( int i = 0 ; i < a . length ( ) ; i ++ ) { char x = a [ i ] ; if ( Char . find ( x ) != Char . end ( ) ) { CharacterIndex [ x ] . push_back ( i ) ; } } int len = INT_MAX ; int flag ; while ( true ) { flag = 1 ; int firstVar , lastVar ; for ( int i = 0 ; i < b . length ( ) ; i ++ ) { if ( i == 0 ) { if ( CharacterIndex . find ( b [ i ] ) == CharacterIndex . end ( ) ) { flag = 0 ; break ; } else { int x = * ( CharacterIndex [ b [ i ] ] . begin ( ) ) ; CharacterIndex [ b [ i ] ] . erase ( CharacterIndex [ b [ i ] ] . begin ( ) ) ; firstVar = x ; lastVar = x ; } } else { int elementFound = 0 ; for ( auto e : CharacterIndex [ b [ i ] ] ) { if ( e > lastVar ) { elementFound = 1 ; lastVar = e ; break ; } } if ( elementFound == 0 ) { flag = 0 ; break ; } } } if ( flag == 0 ) { break ; } len = min ( len , abs ( lastVar - firstVar ) + 1 ) ; } return len ; } int main ( ) { string a = " abcdefababaef " ; string b = " abf " ; int len = minLength ( a , b ) ; if ( len != INT_MAX ) { cout << len << endl ; } else { cout << " Impossible " << endl ; } }