1
\$\begingroup\$

Problem Statement

You are given a string, S , consisting of lowercase English letters.

A string is beautiful with respect S to if it can be derived from S by removing exactly 2 characters.

Find and print the number of different strings that are beautiful with respect to S.

Input Format

A single string of lowercase English letters denoting S.

Output Format

Print the number of different strings that are beautiful with respect to S.

Sample Input

abba

Sample Output

4

Explanation

The following strings can be derived by removing characters from S: ab, bb, ba, ab, ba, aa and bb.

This gives us our set of unique beautiful strings, B = {ab, ba, aa, bb} as |B| = 4, we print 4

Here is my solution but it's not using dynamic programming. I am not getting any hints about how it can be solved via a DP approach.

function beautifulStrings(str) {
    const res = new Set()

    for (let i = 0; i < str.length - 1; i++) {
        for (let j = i + 1; j < str.length; j++) {
            let s = str.split('')
            s[i] = undefined
            s[j] = undefined
            res.add(s.join(''))
        }
    }

    return res.size
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.