Question

D.E. Shaw | OA | SDE-Internship | Coding Questions and Solutions | 2023 | Set-2

Answer 1

Section 2 - Chocolate Shop (Coding, 30 mins)

 

Problem statement: Mary wants to buy some chocolates from a shop. The chocolates in the shop are marked in lowercase english alphabets ('a' to 'z'). Also the shop has divided it's chocolates in to small sets, and assigns a unique set to each customer. Customers can buy chocolates from set s using the below given methods.

 

• Method 1: Buy the enitre set at once
• Method 2: Buy the first i chocolates in the est, i.e. s[1: i] when s[1:i] = s[i+1 : 2i] (where 1 <= i < i+1 <= 2i <= length of s). This mean substring s[i+1 : 2i] and prefix s[1: i] are identical

 

The given set can be bought in multiple steps. And in each step, either of the methods mentioned above can be used. The more the number of steps, the more is the discount a customer can avail. Help Mary to compute the maximum number of steps required to buy the entire set of chocolate.

 

Example:

 

• Input - abbabb
• Output - 2
• Explanation - setp1: Prefix "abb" is bought according to method 2
  step 2: no other identical substring can be formed, hence remaining string "abb" is bought acc to method 1