ENCDEC07-Editorial

PROBLEM LINK:

Practice
Contest

Author: Shloka Mahesheka
Tester: Sunita Sen

DIFFICULTY:

MEDIUM

PROBLEM:

Given a string S and a number k. Find the number of distinct characters in the kth lexicographic smallest suffix of S.

QUICK EXPLANATION:

Sort all the suffix of the string. Number of distinct characters in the kth smallest suffix is the answer.This can be done using suffix array in the given constraints.

EXPLANATION:

After each rotation, the barrier shifts lefts.
After all rotations are done,the letters at the right of barrier are removed.
All the rotations after this, form suffixes of the string.
For string S , the i-th suffix of S is the substring S[iā€¦nāˆ’1].

A suffix array is a sorted array of all suffixes of a given string.

After suffix array is formed, the number of distinct characters in the (k-1)th suffix is the answer.

TIME COMPLEXITY:

The time complexity is O(n logn logn) , where n is length of the string.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
struct store
{
	int index;
	int rank[2]; 
};
int cmp(struct store a, struct store b)
{
	return (a.rank[0] == b.rank[0])? (a.rank[1] < b.rank[1] ?1: 0):
		(a.rank[0] < b.rank[0] ?1: 0);
}
int *function1(string cosmos, int n)
{
	struct store quantam_list[n];
	for (int i = 0; i < n; i++)
	{
		quantam_list[i].index = i;
		quantam_list[i].rank[0] = char(cosmos[i] - 'a');
		quantam_list[i].rank[1] = ((i+1) < n)? char(cosmos[i + 1] - 'a'): -1;
	}
	sort(quantam_list, quantam_list+n, cmp);
	int ind[n];
	for (int k = 4; k < 2*n; k = k*2)
	{
		int rank = 0;
		int prev_rank = quantam_list[0].rank[0];
		quantam_list[0].rank[0] = rank;
		ind[quantam_list[0].index] = 0;
		for (int i = 1; i < n; i++)
		{
			if (quantam_list[i].rank[0] == prev_rank &&
					quantam_list[i].rank[1] == quantam_list[i-1].rank[1])
			{
				prev_rank = quantam_list[i].rank[0];
				quantam_list[i].rank[0] = rank;
			}
			else 
			{
				prev_rank = quantam_list[i].rank[0];
				quantam_list[i].rank[0] = ++rank;
			}
			ind[quantam_list[i].index] = i;
		}
		for (int i = 0; i < n; i++)
		{
			int nextindex = quantam_list[i].index + k/2;
			quantam_list[i].rank[1] = (nextindex < n)?
			quantam_list[ind[nextindex]].rank[0]: -1;
		}
		sort(quantam_list, quantam_list+n, cmp);
	}
	int *relative_pattern = new int[n];
	for (int i = 0; i < n; i++)
		relative_pattern[i] = quantam_list[i].index;
	return relative_pattern;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
    	int n,k;
    	cin>>n>>k;
    	string cosmos;
    	cin>>cosmos;
    	int *relative_pattern = function1(cosmos, n);
    	set<char> password;
    	for(int i=relative_pattern[k-1];i<n;++i)
       	password.insert(cosmos[i]);
    	cout<<password.size()<<"\n";
	}
	return 0;
}
1 Like