Problemi 149

Kërkesa

Në një varg S me shkronja të vogla të alfabetit (anglisht), gjeni se sa nënvargje përmbajnë N bashkëtingëllore të njëpasnjëshme.

Referenca: https://code.google.com/codejam/contest/2437488/dashboard#s=p0&a=0

Shembull

$ cat input.txt
4
quartz 3
straight 3
gcj 2
tsetse 2

$ python3 prog.py < input.txt
4
quartz 3
straight 3
gcj 2
tsetse 2

Për çdo rast testimi jepet vargu S dhe numri N.

Zgjidhja 1

Sqarime

Shqyrtojmë të gjitha nënvargjet e mundshme, dhe për çdo nënvarg kontrollojmë nëse përmban n bashkëtingëllore të njëpasnjëshme.

Koha e kësaj zgjidhje është e rendit \(O(L^3)\).

Zgjidhja 2

Sqarime

Kjo zgjidhje shfrytëzon faktin që nqs një nënvarg që fillon te i dhe mbaron te j përmban n bashkëtingëllore të njëpasnjëshme, atere edhe të gjitha nënvargjet e tjera që fillojnë në i dhe mbarojnë në j+1, j+2, e deri në L do përmbajnë të paktën n bashkëtingëllore të njëpasnjëshme.

Kjo zgjidhje është e rendit \(O(L^2)\).