ENGLISH getting TLE in first 2 cases only.......help(without trie implementation)

Used approach:m1 maps all string (prefix,suffix)->no.of time and m2 maps to its length(hash)
eg: string abcd
m1(a,d)->1(no., times) m2(a,d)->1(length)
m1(ab,cd)->1 m2(ab,cd)->1
m1(abc,bcd)->1 …->3
m1(abcd,abcd)->1 …->4
and sort according to length then coming from bottom(descending order) and decreasing no. of times for the removed string which is already considered in some pair(dehash).
Problem - https://www.codechef.com/problems/ENGLISH

My submission - https://www.codechef.com/viewsolution/28963265

you can also modify each strings as follows

(taking one character from first and last then again second and second last.)
if you observe here only prefix we need to match(basically it is a combination of prefix and suffix).

so if you sort the array of new strings and apply greedy approach then it would be correct ans.
my Solution : My solution

1 Like

nice one really awesome logic, but can you help in mine logic why i am getting TLE in 2 cases

1 Like

The string concatenation on lines 54 and 55 makes the solution slow

I had the same solution too

Yeah Sure…
I was also implementing the same approach before this actual solution.
In ur approach you are creating 1 string for each character.
in worst case there will be 10^5 strings and total lengths of Strings will be approx(10^10 or O(n^2)). It seems to be correct but in worst case it will give you TLE.

Apply ur logic for these 4 String and calculate how many character u are getting.


It will be order of O(n^2).

no no, i think you missed this line in question " * the sum of |W1|+|W2|+…+|WN||over all test cases does not exceed 10^5"

after using push_back() it’s still showing same TLE.