Although in the intended algorithm I can see why it's O(S). However, the python operations aren't taken into account.

startswith() and prefix[:-1] are each doing a linear operation. startswith() still has to do the iteration to check if prefix exists and prefix[:-1] has to create a copy. In the case that all strings are equal, this could be very costly.

Please correct me if I'm wrong.

    def longestCommonPrefix(self, strs):
        if not strs: return ""  
        prefix = strs[0] 
        for string in strs[1:]: 
            while not string.startswith(prefix):  # O(M) time complexity where M is size of prefix
                prefix = prefix[:-1]  # O(M) time complexity where M is size of prefix
                if not prefix: return "" 
        return prefix