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

general
1

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 - ENGLISH Problem - CodeChef

My submission - CodeChef: Practical coding for everyone

2

you can also modify each strings as follows
abcd–>adbccbda
pqpp–>ppqppqpp

(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.
Thanks
my Solution : My solution

1 Like
4

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

1 Like
5

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

I had the same solution too

6

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.

abcd
efgh
ijkl
mnop

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

7

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"

8

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