Failing final test case: Time limit exceeded


  • 0
    T

    I made a java solution that fails the last test case, and I am struggling to see how to make it faster. Am I missing something or is java too slow for these contests?

    public class Solution {
        
        class Helper {
            String str;
            int idx;
            int len;
            int repetitions;
            
            public Helper(String str) {
                this.str = str;
                idx = 0;
                len = str.length();
                repetitions = 0;
            }
            
            public void addChar(char c) {
                if (str.charAt(idx) == c) {
                    updateState();
                }
            }
            
            private void updateState() {
                if (++idx >= len) {
                    idx = 0;
                    repetitions++;
                }
            }
            
            public int getRepetitions() {
                return repetitions;
            }
        }
        
        public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
            Helper helper = new Helper(s2);
            for (int i = 0; i < n1; i++) {
                for (int j = 0; j < s1.length(); j++) {
                    helper.addChar(s1.charAt(j));
                }
            }
            return helper.getRepetitions() / n2;
        }
    }
    

  • 0

    @tjwhalen This is a tricky problem and your solution is too straightforward. According to problem's max input size your solution can have up to 10^8 of addChar method calls. It's too slow to pass.


  • 0
    T

    Yeah you are right. I implemented the same thing in c++ and it still got time exceeded. I looked at some other solutions and they did more clever things. I just did a brute force way and ignored input sizes. See ya next week!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.