HackerRank 'String Construction' Solution

Martin Kysel · September 18, 2018

Short Problem Definition:

Amanda has a string of lowercase letters that she wants to copy to a new string. She can perform the following operations with the given costs. She can perform them any number of times to construct a new string p:

  • Append a character to the end of string p at a cost of 1 dollar.
  • Choose any substring of p and append it to the end of at no charge.

String Construction


time complexity is O(N)

space complexity is O(N)


The solution sounds too easy, but it is still very simple. A substring of length 1 is still a substring. Each character in the final string needs to be copied once for 1$. Each other occurrence of that string can be copied for 0$. Aka just count the number of distinct letters in the expected string.


def stringConstruction(s):
    return len(set(s))

Twitter, Facebook