HackerRank Repeated Strings问题：我的JavaScript代码为何内存溢出？

Hey there! Let's walk through why your code is hitting that out-of-memory error and how to solve it efficiently.

The Root Cause of the Memory Problem #

Your current approach tries to build a full string of length 10^12 (that's 1 trillion characters!) in the variable nStrings. Even if each character only took 1 byte of memory, that's 1 terabyte of data—way more than any regular computer can handle. On top of that, your nested loops are extremely inefficient, making the problem worse by repeatedly appending characters to the string.

The Efficient Fix: Calculate Instead of Building #

Instead of constructing the massive string, we can use basic math to compute the number of 'a's without ever creating it. Here's the breakdown:

• Count 'a's in the original string: First, figure out how many 'a's are present in one copy of s.
• Calculate full repetitions: Find how many complete times s fits into n characters. Multiply this number by the count of 'a's per string.
• Count remaining characters: Compute the leftover characters after the full repetitions, then count how many 'a's are in that partial slice of s.
• Sum the totals: Add the two counts together to get the final number of 'a's.

Optimized JavaScript Code #

const countRepeatedAs = (s, n) => {
    // Count 'a's in one full string
    const countPerString = s.split('').filter(char => char === 'a').length;
    // Number of complete times s repeats
    const fullRepeats = Math.floor(n / s.length);
    // Remaining characters after full repeats
    const remainingLength = n % s.length;
    // Count 'a's in the remaining partial string
    const countRemaining = s.slice(0, remainingLength).split('').filter(char => char === 'a').length;
    
    return fullRepeats * countPerString + countRemaining;
};

// Test with your input
console.log(countRepeatedAs('a', 1000000000000)); // Output: 1000000000000

Why This Works #

• Memory efficiency: We never create a string longer than the original s, so memory usage stays tiny no matter how big n is.
• Time efficiency: The algorithm runs in O(length of s) time, which is blazing fast even for large n values like 1 trillion.

内容的提问来源于stack exchange，提问作者Chaitanya V