Bài tập mã hóa xâu C++

[Duc_Thanh_Trinh (Đức Thành Trịnh)]

các cao nhân chỉ giúp em bài này đc không ạ, khoai quá, em nghĩ mãi mà không ra

[SITUVN.gcd]

Chuỗi S luôn luôn là chuỗi có độ dài chẵn và số lượng từng kí tự luôn chẵn (chia hết cho 2).
Ý tưởng ban đầu: loại bỏ 1 kí tự của từng cặp kí tự giống nhau trong chuỗi.

[Stanley00 (Stanley)]

Bài này chưa biết làm gì thì cứ làm theo cách ngu ngốc nhất có thể thôi:

1. Loại bỏ ký tự từng cặp như SITUVN nói => xác định chuỗi cần tìm là hoán vị của phân nửa chuỗi ban đầu
2. Sinh tất cả hoán vị A của chuỗi ở bước 1 theo thứ tự từ điển cho đến khi nào tìm được chuỗi thỏa điều kiện: Reverse(A) là chuỗi con của S

Code ví dụ:

from itertools import permutations as perm
import re

def rev(s):
	return reversed(s)

def half(s):
	return sorted(s)[::2]

def issub(a, b):
	return re.search('.*'.join(a), b)

def f(s):
	return ''.join(next(filter(lambda h: issub(rev(h), s), perm(half(s)))))

for s in set(perm('aabbccddee')):
	s=''.join(s)
	print(s, f(s))

Phần nâng cao: Sau khi nhìn thử pattern input và output, ta sẽ có 1 số nhận xét sau:

• Chuỗi A là chuỗi con của chuỗi S đảo ngược (Reverse(S))
• Độ dài của chuỗi A bằng một nửa chuỗi S
• Tần suất các ký tự của A đúng bằng một nửa chuỗi S
  => Cách giải là tìm chuỗi con nhỏ nhất của Reverse(S) thỏa điều kiện bảng tần suất

Mã giả

def f(s):
	d=Counter(s)
	dh={k:d[k]//2 for k in d}

	r = ''
	i=0
	s=rev(s)
	while len(r) < len(s) // 2:
		m = -1
		while True:
			c = s[i]
			if dh[c] > 0 and (m < 0 or c < s[m]):
				m = i
			d[c] -= 1
			if d[c] < dh[c]:
				break
			i += 1
		for j in range(m+1, i+1):
			d[s[j]] += 1
		dh[s[m]] -= 1
		r += s[m]
		i = m + 1
	return r

[Duc_Thanh_Trinh (Đức Thành Trịnh)]

cảm ơn các bác đã góp ý ạ, em sẽ thử nghĩ theo hướng đó xem sao