Stack
Array
Hash Table
Math
Sliding Window
Description
You are given an integer array nums
and a positive integer k
.
The frequency score of an array is the sum of the distinct values in the array raised to the power of their frequencies , taking the sum modulo 109 + 7
.
For example, the frequency score of the array [5,4,5,7,4,4]
is (43 + 52 + 71 ) modulo (109 + 7) = 96
.
Return the maximum frequency score of a subarray of size k
in nums
. You should maximize the value under the modulo and not the actual value.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,1,1,2,1,2], k = 3
Output: 5
Explanation: The subarray [2,1,2] has a frequency score equal to 5. It can be shown that it is the maximum frequency score we can have.
Example 2:
Input: nums = [1,1,1,1,1,1], k = 4
Output: 1
Explanation: All the subarrays of length 4 have a frequency score equal to 1.
Constraints:
1 <= k <= nums.length <= 105
1 <= nums[i] <= 106
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def maxFrequencyScore ( self , nums : List [ int ], k : int ) -> int :
mod = 10 ** 9 + 7
cnt = Counter ( nums [: k ])
ans = cur = sum ( pow ( k , v , mod ) for k , v in cnt . items ()) % mod
i = k
while i < len ( nums ):
a , b = nums [ i - k ], nums [ i ]
if a != b :
cur += ( b - 1 ) * pow ( b , cnt [ b ], mod ) if cnt [ b ] else b
cur -= ( a - 1 ) * pow ( a , cnt [ a ] - 1 , mod ) if cnt [ a ] > 1 else a
cur %= mod
cnt [ b ] += 1
cnt [ a ] -= 1
ans = max ( ans , cur )
i += 1
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47 class Solution {
private final int mod = ( int ) 1e9 + 7 ;
public int maxFrequencyScore ( int [] nums , int k ) {
Map < Integer , Integer > cnt = new HashMap <> ();
for ( int i = 0 ; i < k ; ++ i ) {
cnt . merge ( nums [ i ] , 1 , Integer :: sum );
}
long cur = 0 ;
for ( var e : cnt . entrySet ()) {
cur = ( cur + qpow ( e . getKey (), e . getValue ())) % mod ;
}
long ans = cur ;
for ( int i = k ; i < nums . length ; ++ i ) {
int a = nums [ i - k ] ;
int b = nums [ i ] ;
if ( a != b ) {
if ( cnt . getOrDefault ( b , 0 ) > 0 ) {
cur += ( b - 1 ) * qpow ( b , cnt . get ( b )) % mod ;
} else {
cur += b ;
}
if ( cnt . getOrDefault ( a , 0 ) > 1 ) {
cur -= ( a - 1 ) * qpow ( a , cnt . get ( a ) - 1 ) % mod ;
} else {
cur -= a ;
}
cur = ( cur + mod ) % mod ;
cnt . put ( b , cnt . getOrDefault ( b , 0 ) + 1 );
cnt . put ( a , cnt . getOrDefault ( a , 0 ) - 1 );
ans = Math . max ( ans , cur );
}
}
return ( int ) ans ;
}
private long qpow ( long a , long n ) {
long ans = 1 ;
for (; n > 0 ; n >>= 1 ) {
if (( n & 1 ) == 1 ) {
ans = ans * a % mod ;
}
a = a * a % mod ;
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 class Solution {
public :
int maxFrequencyScore ( vector < int >& nums , int k ) {
using ll = long long ;
const int mod = 1e9 + 7 ;
auto qpow = [ & ]( ll a , ll n ) {
ll ans = 1 ;
for (; n ; n >>= 1 ) {
if ( n & 1 ) {
ans = ans * a % mod ;
}
a = a * a % mod ;
}
return ans ;
};
unordered_map < int , int > cnt ;
for ( int i = 0 ; i < k ; ++ i ) {
cnt [ nums [ i ]] ++ ;
}
ll cur = 0 ;
for ( auto & [ k , v ] : cnt ) {
cur = ( cur + qpow ( k , v )) % mod ;
}
ll ans = cur ;
for ( int i = k ; i < nums . size (); ++ i ) {
int a = nums [ i - k ], b = nums [ i ];
if ( a != b ) {
cur += cnt [ b ] ? ( b - 1 ) * qpow ( b , cnt [ b ]) % mod : b ;
cur -= cnt [ a ] > 1 ? ( a - 1 ) * qpow ( a , cnt [ a ] - 1 ) % mod : a ;
cur = ( cur + mod ) % mod ;
ans = max ( ans , cur );
cnt [ b ] ++ ;
cnt [ a ] -- ;
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 func maxFrequencyScore ( nums [] int , k int ) int {
cnt := map [ int ] int {}
for _ , v := range nums [: k ] {
cnt [ v ] ++
}
cur := 0
const mod int = 1e9 + 7
qpow := func ( a , n int ) int {
ans := 1
for ; n > 0 ; n >>= 1 {
if n & 1 == 1 {
ans = ans * a % mod
}
a = a * a % mod
}
return ans
}
for k , v := range cnt {
cur = ( cur + qpow ( k , v )) % mod
}
ans := cur
for i := k ; i < len ( nums ); i ++ {
a , b := nums [ i - k ], nums [ i ]
if a != b {
if cnt [ b ] > 0 {
cur += ( b - 1 ) * qpow ( b , cnt [ b ]) % mod
} else {
cur += b
}
if cnt [ a ] > 1 {
cur -= ( a - 1 ) * qpow ( a , cnt [ a ] - 1 ) % mod
} else {
cur -= a
}
cur = ( cur + mod ) % mod
ans = max ( ans , cur )
cnt [ b ] ++
cnt [ a ] --
}
}
return ans
}
GitHub