Repeated Substring Pattern Detection in String

amazon Given a non-empty string s, determine if it can be constructed by taking a substring of it and appending multiple copies of the substring together. For example, given the string 'abab', you return True, because it can be constructed by repeating the substring 'ab'. Given the string 'aba', it cannot be constructed by repeating any substring. Implement a function repeatedSubstringPattern to solve the problem. Assume the input only contains lowercase English letters. If a more advanced data structure can simplify the algorithm, consider using it. Input size: 1 <= length of the string <= 10^4. Test cases: 'abab', 'aba', 'abcabcabc', 'abcdef'. Example Input abab