Leetcode 1915 - Number of Wonderful Substrings - Normal Code VS Iterator Code

[rony0000013]

I was coding a leetcode Problem https://leetcode.com/problems/number-of-wonderful-substrings/ I coded one accepted solution

impl Solution {
    pub fn wonderful_substrings(word: String) -> i64 {
        let mut ans: i64 = 0;
        let mut v = vec![0; 1024];
        v[0] = 1;
        let mut x = 0;

        for c in word.chars() {
            x ^= 1 << (c as u8 - b'a') as usize;
            ans += v[x];
            for i in 0..10 {
                ans += v[x ^ (1 << i)];
            }
            v[x] += 1;
        }
        ans
    }
}

and similarly i coded a iterator style version of the code

impl Solution {
    pub fn wonderful_substrings(word: String) -> i64 {
        word
        .chars()
        .fold((0usize, 0i64, 
        {let mut v =[0i64; 1024]; v[0]=1; v}),
        |(mut x, mut ans, mut v), c| {
            x ^= 1 << (c as u8 - 97);
            ans += v[x];
            ans += (0..10).map(|i| v[x ^ (1 << i)]).sum::<i64>();
            // for i in 0 .. 10 {
            //     ans += v[x ^ (1 << i)];
            // }
            v[x] += 1;
            (x, ans, v)
        }).1
    }
}

but the problem is the iterator code is getting TLE. So, I have a question that why the Iterator code is getting TLE and not the normal code ?

[drewtato]

Looks like the only difference is that the for loop one uses a Vec, while the iterator one uses an array. Try changing the iterator one.

let mut v = vec![0i64; 1024];

Normally this shouldn't matter, but because fold moves the state parameter around a lot, it might be copying the entire array when it doesn't need to.

Another thing you can do is make the array before, and pass in a reference.

let mut v = [0i64; 1024];
v[0] = 1;
word
    .chars()
    .fold((0usize, 0i64, &mut v),
        ...

[rony0000013]

yes, You were right the array was copied which took 1000+ms
but when I passes in mut refference or a Vector instead of an array then the time took was 2ms.

As It turns out using array instead of Vector is not always efficient.