Number of Distinct Subsequences

Given a string, find counts of distinct subsequences of it.

Hint

Start with an empty list. Initially add an empty string to this list. This list will store all the combinations we find.

Iterate through each character. For each character in the input string, create new combinations with each existing one in the list by adding the current character to the end of the existing one. Add all the newly created combinations to the list.

Continue this process for each character in the input string.

Python
Javascript

# Python implementation

data = 'abc'
output = ['']

for i in range(len(data)):
  c = data[i]

  for j in output[:]:
    output.append(j + c)

print(len(output))

// Javascript implementation

const data = 'abc';
const output = [''];

for (let i = 0; i < data.length; i++) {
  const c = data.at(i);

  for (let j of [...output]) {
    output.push(j + c);
  }
}

console.log(output.length);