Удаление с начала через s = s[1:] - O(1) по времени, но сдвигает указатель по базовому массиву; весь массив остаётся в памяти до сборки мусора. Удаление через append(s[:0], s[1:]...) копирует хвост - O(n). Для частого удаления с начала рассмотрите очередь на кольцевом буфере или списке.