Từ xâu \(T\) ta tách thành 2 mảng sau:

• \(c[i]\): ký tự thứ i (từ tập kí tự \(a...z\))
• \(s[i]\): số lượng ký tự liên tiếp tương ứng

Gọi \(f[i][j]\) là số cách chọn khi xét đến vị trí \(i\) trong mảng \(c\), đã chọn xong đến ký tự thứ \(j\) trong xâu \(P\).

Ta có:
\(f[0][0]=1\).
\(f[i+1][j+t]+=f[i][j] * C(s[i+1],t)\) (đk: các ký tự từ \(j+1->j+t\) trong xâu \(P = c[i+1]\)).

Ta có thể tính \(C(s[i+1],t)\) trong \(O(1)\):

• Chuẩn bị trước mảng \(nd[0...m]\) với \(nd[i]=i^{(1e9+7)}\)
• \(C(n,k)=C(n,k-1) * (n-k+2)*nd[k+1]\)

Đpt: \(O(n * m*m)\)

Lời giải của BTC cuộc thi