Problema
Take every contiguous window of span digits and multiply its digits. Return the largest product. Leading zeros are ordinary digits; a window containing zero has product zero. Do not reorder or skip digits.
Implement largest_adjacent_digit_product(digits, span).
Input
digits: The digit sequence, including any leading zeros.
span: The exact number of adjacent digits in a window.
Output
Return the greatest product over all windows of this width.
Vincoli
1 ≤ digit-string length ≤ 100,000. Characters are 0…9. 1 ≤ span ≤ min(18, length). All products fit signed 64-bit.
Esempi
Input:
span = 2
digits = "23405"
Output atteso:
expected = 12Input:
long long span = 2;
std::string digits = "23405";
Output atteso:
long long expected = 12;Input:
long span = 2;
string digits = "23405";
Output atteso:
long expected = 12;Spiegazione
The windows 23, 34, 40, and 05 have products 6, 12, 0, and 0. The largest is 12.
Input:
span = 3
digits = "102"
Output atteso:
expected = 0Input:
long long span = 3;
std::string digits = "102";
Output atteso:
long long expected = 0;Input:
long span = 3;
string digits = "102";
Output atteso:
long expected = 0;Spiegazione
There is only one width-three window. It contains zero, so 1 × 0 × 2 = 0.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Uno zero dentro una finestra porta quel prodotto a zero, quindi solo tratti contigui senza zeri possono contribuire al massimo.
Suggerimento 2
Usa una sliding window o tieni traccia dei prodotti sui run di cifre per evitare di ricalcolare ogni intervallo da zero.
Suggerimento 3
Attenzione alla lunghezza esatta dello span: gli zeri iniziali contano come cifre, e se lo span supera un blocco senza zeri, il prodotto è zero.
Complessità attesa
tempo O(n), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.