Longest Repeated (Scattered) Subsequence in a String
The special case of $k = n/2$ is the same problem as this CST.SE question How hard is unshuffling a string? asks.
Buss and Soltys proved NP-completeness of this problem [1] by reducing 3-Partition problem to this problem.

[1]: Buss, Sam, and Michael Soltys. &quot;Unshuffling a square is NP-hard.&quot; Journal of Computer and System Sciences 80.4 (2014): 766-776.