PROBLEM LINK:Author and Editorialist : Dhruv Mahajan DIFFICULTY:Simple PREREQUISITES:DP EXPLANATION:Store the occurance of A,B,C in a dp array. Let, Ai = Number of ‘A’s in S between the indexes 1 and i (inclusive). Bi = Number of ‘B’s in S between the indexes 1 and i (inclusive). Ci = Number of ‘C’s in S between the indexes 1 and i (inclusive). Let’s consider the substring Sj...i : Number of ‘A’s in that substring = Ai  Aj1 Number of ‘B’s in that substring = Bi  Bj1 Number of ‘C’s in that substring = Ci  Cj1 So for that substring to be good: Ai  Aj1 = Bi  Bj1 = Ci  Cj1 Alternatively the following two conditions are enough for that substring to be good: Ai  Bi = Aj1  Bj1 Ai  Ci = Aj1  Cj1 Find all the subtrings in two loops match the occurance of A,B,C from the dp array's. SOLUTION:
This question is marked "community wiki".
asked 16 Oct '15, 19:14
