Напишите функцию преобразования строки из camelCase в snake_case. Нельзя использовать регулярные выражения, коды символов или жёстко заданный список символов; решение должно работать универсально. Оцените временную и пространственную сложность.