I recently came across this problem in the LC weekly, and came up with a dp+hashing solution. However, most accepted users, as well as the the intended solution, use a trie and iterates through the string n times. I discarded any N^2 ideas because I thought the constraint of 5e4 would be too large for N^2. Do you believe this is a result of weak testcases or is it actually reasonable to consider N^2 solutions with the constraints given? I always thought the rule of thumb for N^2 was 1e4, and believe these solutions would not survive if there was a hacking phase.

Problem: https://leetcode.com/problems/construct-string-with-minimum-cost/

Edit: As one user pointed out, the input: "aaa..." (length 50k) ["aaa..." (length 25k), "a"] [1,1], results in N^2 complexity in the worst case and would likely TLE most if not all of the trie DP solutions.