Increasing subsequences P96556


Statement
 

pdf   zip

thehtml

Write a program that computes how many strictly increasing subsequences with at least two letters are contained in a given word. For instance, the word arrow (we have written the second r in bold italics to distinguish it) contains the increasing subsequences arw, ar, arw, ar, aow, ao, aw, rw, rw and ow.

Input

Input consists of several cases, each with a word made up of between 1 and 100 lowercase letters.

Output

For every case, print the number of strictly increasing subsequences with at least two letters contained in the word. That number will always be less than 109.

Public test cases
  • Input

    arroz
    petate
    az
    za
    t
    aaaa
    abcdefghij
    abcdefghijabcdefghijabcdefghijabcdefghij
    aaaaaaaaaabbbbbbbbbbyyyyyyyyyyzzzzzzzzzz
    

    Output

    10
    6
    1
    0
    0
    0
    1013
    66263
    14600
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++ Python