Getting WA in Ternary String Educational Codeforces Round 87 (Rated for Div. 2)

1

#include
#include
#include
#include
#define ll long long
using namespace std;

int main()
{
int t;
cin >> t;
while (t–)
{
string s;
cin >> s;

	int v[3];
	
	for (int i = 0; i < 3; i++)
	{
		v[i] = -1;
	}

	
	//int num = 3;
	bool tr[3] = { 0 };
	int flg = 0;
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == '1' && tr[0] == 0)
			flg++,tr[0] = 1;

		if (s[i] == '2' && tr[1] == 0)
			flg++, tr[1] = 1;
		if (s[i] == '3' && tr[2] == 0)
			flg++, tr[2] = 1;



		if(v[0]==-1 || v[1]==-1 || v[2]==-1)
		{
			//cout << "working";

			if (s[i] == '1')
				v[0] = i;

			if (s[i] == '2')
				v[1] = i;

			if (s[i] == '3')
				v[2] = i;
		}
		else 
		{
		//	cout << "heyyyyyy";
			if (s[i] == '1')
			{
				if(abs(v[0]-v[2])+abs(v[0]-v[1])+abs(v[1]-v[2]) > abs(i - v[2]) + abs(i - v[1]) + abs(i - v[2]))
					v[0]=i;
			}
			if (s[i] == '2')
			{
				if (abs(v[0] - v[2]) + abs(v[0] - v[1]) + abs(v[1] - v[2]) > abs(v[0] - v[2]) + abs(v[0] - i) + abs(v[2] - i))
					v[1] = i;
			}
			if (s[i] == '3')
			{
				if (abs(v[0] - v[2]) + abs(v[0] - v[1]) + abs(v[1] - v[2]) > abs(v[0] - i) + abs(v[0] - v[1]) + abs(v[1] - i))
					v[2] = i;
			}
		}
		
		
	}
	//for (int i = 0; i < 3; i++)
		//cout << v[i] << " ";

	sort(v, v+3);
	

	//cout << "\nans:";

	if (flg < 3)
		cout << "0\n";
	else
	{
		cout << v[2]-v[0] + 1 << "\n";
	}

}

}

2

just search “smallest substring with unique characters gfg” on goolge or just read the tutorial of this problem provided on codeforces , and with the given constraints and time limit of 2 sec , bruteforce approach would also work

1 Like
3

you can watch the editorial I made for this problem and solve this problem using binary search.

Ternary String

2 Likes
4

what is wrong in my code i stored index of 1,2,3 .And updated if they are minimizing length of substring containing 1,2,3.