Strings
Qué vamos a ver hoy
| Min | Tema |
|---|---|
| 0–20 | Indexación, slicing y palíndromos |
| 20–30 | Inmutabilidad: construir con lista y join |
| 30–45 | Métodos de strings |
| 45–60 | ord/chr, frecuencias y anagramas |
| 60–70 | Números y strings: dígitos y bases |
| 70–80 | Comparación lexicográfica |
| 80–90 | Problemas de la práctica |
Índices y slicing
Cada carácter tiene un índice positivo y uno negativo.
s[inicio:fin:paso]
s[i]es el carácter en la posición i.s[-1]es el último.s[a:b]va desde a hasta b − 1. El fin no se incluye.- Si falta el inicio o el fin, se toma desde el borde.
s[::-1]recorre al revés: invierte el string.- Un slice crea un string nuevo: cuesta O(b − a).
s[20]daIndexError, peros[2:20]no da error.
Un palíndromo se lee igual al revés
# forma corta: crea una copia invertida, O(n)
es_pal = s == s[::-1]
# dos punteros: no crea copias
i, j = 0, len(s) - 1
es_pal = True
while i < j:
if s[i] != s[j]:
es_pal = False
break
i += 1
j -= 1
Las dos son O(n). La de dos punteros sirve cuando hay que saber dónde falla, por ejemplo para quitar un carácter.
Los strings son inmutables
Un string no se puede modificar. Cada cambio crea uno nuevo.
Construir un string con una lista
s = "hola"
s[0] = "H" # TypeError: 'str' object does not
# support item assignment
# cambiar un carácter: pasar por una lista
t = list(s)
t[0] = "H"
s = "".join(t) # "Hola"
# construir una respuesta larga
partes = []
for c in s:
partes.append(c.upper())
res = "".join(partes) # O(n) en total
s = s + c copia los caracteres de s en un string nuevo. En un bucle de n vueltas, se copian 1 + 2 + … + n ≈ n²/2 caracteres.
2·10⁵ concatenaciones
s = c + s (al inicio)0.44 ss += c0.44 s"".join0.002 sEn PyPy, s += c copia el string completo en cada vuelta: es O(n²). Con 10⁶ concatenaciones tardó 11.7 s; con join, 0.015 s.
PyPy 3.11, Apple M4.
Métodos de strings
Funciones que ya vienen en Python y recorren el string en C.
Probar los métodos
| Método | Devuelve |
|---|---|
split() | lista de palabras |
strip() | sin espacios en los bordes |
count(t) | apariciones sin solaparse |
find(t) | primer índice o −1 |
replace(a, b) | string con a cambiado por b |
startswith(t) | True o False |
upper() / lower() | mayúsculas / minúsculas |
isdigit() | ¿todos son dígitos? |
Caracteres y frecuencias
Cada carácter es un número. Eso permite usarlo como índice.
Cada carácter tiene un código
ord("a") # 97
chr(98) # "b"
ord(c) - ord("a") # posición de c: 0..25
chr(ord("a") + i) # letra número i
ord("A") # 65: mayúsculas antes
Cifrado César: chr((ord(c) - 97 + k) % 26 + 97). El % 26 hace que después de la z siga la a.
Contar letras con un arreglo de 26
cnt = [0] * 26
for c in s:
cnt[ord(c) - 97] += 1
# con la biblioteca
from collections import Counter
cnt = Counter(s) # {'a': 3, 'n': 2, 'b': 1}
El arreglo de 26 sirve cuando las letras son minúsculas. Counter sirve para cualquier carácter o palabra.
Dos palabras son anagramas si tienen las mismas frecuencias
# O(n log n) sorted(a) == sorted(b) # O(n) Counter(a) == Counter(b)
Cada letra tiene dos barras: la de a a la izquierda (azul) y la de b a la derecha (verde). Las letras en rojo tienen frecuencias distintas.
Números y strings
Dígitos, sumas de dígitos y cambios de base.
De decimal a binario, dividiendo entre 2
bin(13) # '0b1101'
bin(13)[2:] # '1101'
int("1101", 2) # 13
int("ff", 16) # 255
# suma de dígitos
sum(map(int, str(n)))
# a una base b cualquiera
def a_base(n, b):
if n == 0:
return "0"
d = []
while n > 0:
d.append(str(n % b))
n //= b
return "".join(reversed(d))
Comparación lexicográfica
El orden del diccionario, carácter por carácter.
Gana el primer carácter distinto
¿Cuál es menor? Haga clic para ver la respuesta.
Si un string es prefijo del otro, el más corto es menor. Las mayúsculas (65–90) van antes que las minúsculas (97–122).
Problemas de la práctica
Cuatro problemas A de Codeforces y Palindrome Reorder de CSES.
Abreviar palabras y procesar letras
71A · Way Too Long Words
Si una palabra tiene más de 10 letras, se escribe primera letra + cantidad de letras del medio + última letra.
for _ in range(int(input())):
w = input()
if len(w) > 10:
w = w[0] + str(len(w) - 2) + w[-1]
print(w)
"localization" → "l10n"
118A · String Task
Quitar las vocales (incluida la y), poner un punto antes de cada consonante y pasar a minúsculas.
s = input().lower()
res = []
for c in s:
if c not in "aoyeui":
res.append("." + c)
print("".join(res))
"Codeforces" → ".c.d.f.r.c.s"
Comparar sin mayúsculas y contar distintos
112A · Petya and Strings
Comparar dos strings sin distinguir mayúsculas. Imprimir −1, 0 o 1.
a = input().lower()
b = input().lower()
if a < b:
print(-1)
elif a > b:
print(1)
else:
print(0)
236A · Boy or Girl
Si el nombre de usuario tiene una cantidad par de letras distintas, es mujer; si es impar, es hombre.
s = input()
if len(set(s)) % 2 == 0:
print("CHAT WITH HER!")
else:
print("IGNORE HIM!")
Reordenar las letras para formar un palíndromo
s = input()
cnt = [0] * 26
for c in s:
cnt[ord(c) - 65] += 1
impares = [i for i in range(26) if cnt[i] % 2]
if len(impares) > 1:
print("NO SOLUTION")
else:
mitad = []
for i in range(26):
mitad.append(chr(65 + i) * (cnt[i] // 2))
mitad = "".join(mitad)
centro = chr(65 + impares[0]) if impares else ""
print(mitad + centro + mitad[::-1])
Problemas de la práctica
Reglas para strings en Python
- Leer un string con
input()y varias palabras coninput().split(). - Construir respuestas con una lista y
"".join. - Recordar que los métodos y los slices son O(n).
- Contar con un arreglo de 26 o con
Counter. - Comparar números como
int, no como texto.