Did this for a Google mock assessment; was labeled as "easy" but I think I took an approach that might have been more complicated than necessary (I ran out the clock and finished up afterwards), and was wondering if anyone had any feedback / suggestions for the solution I came up with.

Basically, given a string, e.g. "ababab", can you tell me, true or false, if it's possible to construct the whole string just from one of its substrings?

examples:

"ab" -> false
"abab" -> true
"ababab" -> false

My approach (roughly linear time in worst-case, I think, but maybe a bit memory intensive):
Take each character in the main string, and then look ahead and behind it by one. Store 'next' and 'previous' in an ordered tuple as value in a hashtable of the string's unqiue characters.

Basically, if any one character is hashed to too many unique tuples, the overall string has non-homogenous substrings and can't be replicated from just one substring.

Shortcomings: If the problem asked me to return the exact substring that would be repeated, I'm not sure the graph I end up with could be used to reconstruct it. (Although if you started from the tuple hashed to by the very first character in the overall string and interated forward, maybe you could--but I haven't tested this.)

Memory is a bit intensive--each touple is two characters, one tuple per character in the overarching string; one key per character in the string. So 2n + n -> 3n in terms of memory, more or less.

Here is my testing code (finished the solution in a python playground file):

s = Solution()

tests: list[str] = ["abab", "abcab", "ababc", "aba", "abcabcabcabc", "abaababaab", "acaababaab", \
                    "abbbabbba", "abbbaabbba"]
    
for t in tests: 
    print("--------")
    print(t)
    print(s.repeatedSubstringPattern(t))

And here's the actual solution (the print statements might help to visualize what exactly is going on but aren't at all necessary).

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        if len(s) < 2: 
            return False
        
        if len(s) < 3: 
            return s[0] == s[1] 
        
        if len(s) < 4: 
            return s[0] == s[1] and s[1] == s[2]
        
        trie_map: dict[str, set[tuple[str, str]]] = {}
        
        i: int = 0
        for c in s: 
            
            prev_char: str = s[i - 1] if i > 0 else s[-1]
            next_char: str = s[i + 1] if i < len(s) - 1 else s[0]
            
            chars = (prev_char, next_char)
            
            if c in trie_map.keys() and not chars in trie_map[c]: 
                threshold = 3 if c in trie_map[c] or c in chars else 1
                print(f"threshold: {threshold}")
                
                if len(trie_map[c]) >= threshold: 
                    print(f"Failed on {c} -> {chars}")
                    return False
                else: 
                    print(f"continued on threshold {len(trie_map[c])} of {threshold}")
                    print(f"[ {trie_map[c]} ]")
            
            if not c in trie_map.keys():
                trie_map[c] = set()
                 
            trie_map[c].add(chars)
            
            print(f"{c} -> {chars}\n")
            
            i += 1
            
        return True

Thank you for your time! :)