shortest_subsequence.cpp

using namespace std;
#include <bits/stdc++.h>
#define trace(x) cout<<#x<<": "<<x<<" ";

int main(int argc, char const *argv[])
{
	vector<string> v;

	string s;
	getline(cin, s);
	
	string temp = "";

	for (int i = 0; i < s.size(); i++) 
	{
		int asc = s[i];

		if(asc>=97 && asc<=122)
		{
			temp += s[i];
		}
		else
		if(asc>=65 && asc<=90)
		{
			// s[i] = s[i] + 32;
			temp += (char)(s[i] + 32);
		}
		else
		{
			if(temp != "")
				v.push_back(temp);
			temp = "";
		}
	}
	if(temp != "")
		v.push_back(temp);


	int k;
	vector<string> in;
	cin>>k;
	unordered_map<string, int> uin;
	for (int i = 0; i < k; i++) 
	{
		string x;
		cin>>x;
		for (int i = 0; i < x.size(); i++) 
		{
			if(x[i]>=65 && x[i]<=90)
				x[i] = x[i] + 32;	
		}
		in.push_back(x);
		uin[x]++;
	}

	// for (int i = 0; i < v.size(); i++) 
	// {
	// 	cout<<v[i]<<endl;	
	// }
	// for (int i = 0; i < in.size(); i++) 
	// {
	// 	cout<<in[i]<<endl;	
	// }

	int mn = INT_MAX;
	int curr = 0;
	int left = -1;
	int right = -1;

	for (int i = 0; i < v.size(); i++) 
	{
		unordered_map<string, int> umap;
		for (int j = i; j < v.size(); j++) 
		{
			umap[v[j]]++;

			int cnt = 0;

			for(auto it = uin.begin(); it != uin.end(); it++)
			{
				string r = it->first;
				int freq = it->second;

				
				if(umap[r]>=1)
					cnt++;
			}

			if(cnt == uin.size())
			{
				if(mn > (j-i))
				{
					mn = (j-i);
					left = i;
					right = j;
				}
					trace(i);
					trace(j);
					cout<<endl;
			}
		}
	}

	if(left == -1 || right == -1)
	{
		cout<<"NO SUBSEGMENT FOUND"<<endl;
		return 0;
	}


	// for (int i = left; i <= right; i++) 
	// {
	// 	cout<<v[i]<<" ";
	// }
	// cout<<endl;

	temp = "";
	int ind = -1;
	for (int i = 0; i < s.size(); i++) 
	{
		int asc = s[i];

		if(asc>=97 && asc<=122 || asc>=65 && asc<=90)
		{
			temp += s[i];
		}
		else
		{
			if(temp != "")
            {
				ind++;
			    if(ind>=left && ind<=right)
				  cout<<temp<<" ";
            }
			temp = "";
		}
	}
	if(temp != "")
		ind++;
	if(ind>=left && ind<=right)
		cout<<temp<<" ";
	cout<<endl;








	return 0;
}