You are given a string S. Every sub-string of identical letters is replaced by a single instance of that letter followed by the hexadecimal representation of the number of occurrences of that letter. Then, the string thus obtained is further encrypted by reversing it [ See the sample for more clarity ]. Print the Encrypted String.
Note: All Hexadecimal letters should be converted to Lowercase letters.
 
Example 1:
Input:
S = "aaaaaaaaaaa"
Output:
ba 
Explanation: 
aaaaaaaaaaa
Step1: a11 (a occurs 11 times)
Step2: a11 is ab [since 11 is b in
hexadecimal]
Step3: ba [After reversing]
Example 2:
Input:
S = "abc"
Output:
1c1b1a
Explanation: 
abc
Step1: a1b1c1
Step2: 1c1b1a [After reversing]
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function encryptString() which takes a String S and returns the answer.
 
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
Constraints
1 <= |S| <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Greedy algorithms

Starter code: #User function Template for python3

class Solution:
    def encryptString(self, S):
        # code here

Solutions:
from collections import Counter

class Solution:

	def encryptString(self, S):
		arr = list(S)
		ans = []
		char = arr[0]
		count = 1
		for i in range(1, len(arr) + 1):
			if i == len(arr):
				ans.append(char)
				ans.append(hex(count)[2:])
				break
			if arr[i] == char:
				count = count + 1
			else:
				ans.append(char)
				ans.append(hex(count)[2:])
				count = 1
				char = arr[i]
		ans = ans[::-1]
		encrypt = ''.join(ans)
		return encrypt


from collections import Counter

class Solution:

	def encryptString(self, S):
		count = 1
		ans = ''
		for i in range(len(S)):
			if i + 1 < len(S) and S[i] == S[i + 1]:
				count += 1
			else:
				ans = str(hex(count))[2:] + S[i] + ans
				count = 1
		return ans


class Solution:

	def convert(num):
		temp = ''
		while num != 0:
			rem = num % 16
			c = 0
			if rem < 10:
				c = rem + 48
			else:
				c = rem + 87
			temp = temp + chr(c)
			num = num // 16
		return temp

	def encryptString(self, S):
		res = ''
		i = 0
		while i < len(S):
			ch = S[i]
			count = 0
			while i < len(S) and S[i] == ch:
				count = count + 1
				i = i + 1
			hex = Solution.convert(count)
			res = res + ch
			res = res + hex
		return res[::-1]


class Solution:

	def encryptString(self, S):
		rs = S[::-1]
		res = 1
		res_str = ''
		for i in range(1, len(rs)):
			if rs[i] != rs[i - 1]:
				res_str += format(res, 'x') + rs[i - 1]
				res = 1
			else:
				res += 1
		res_str += format(res, 'x') + rs[len(rs) - 1]
		return res_str


class Solution:
	ans = ''

	def encryptString(self, S):
		hexa = {0: '0', 1: '1', 2: '2', 3: '3', 4: '4', 5: '5', 6: '6', 7: '7', 8: '8', 9: '9', 10: 'a', 11: 'b', 12: 'c', 13: 'd', 14: 'e', 15: 'f'}
		count = 1
		ans = S[0]
		for i in range(0, len(S) - 1):
			if S[i] == S[i + 1]:
				count += 1
			else:
				s1 = ''
				while count > 15:
					t1 = count % 16
					s1 = hexa[t1] + s1
					count = int((count - t1) / 16)
				ans = S[i + 1] + hexa[count] + s1 + ans
				count = 1
		s1 = ''
		while count > 15:
			t1 = count % 16
			s1 = hexa[t1] + s1
			count = int((count - t1) / 16)
		ans = hexa[count] + s1 + ans
		return ans


class Solution:

	def encryptString(self, S):
		ans = ''
		c = S[0]
		count = 1
		for i in range(1, len(S)):
			if S[i] == c:
				count += 1
			else:
				ans += c
				hex = ''
				while count:
					rem = count % 16
					if rem < 10:
						hex += chr(48 + rem)
					else:
						hex += chr(97 + rem - 10)
					count //= 16
				ans += hex
				count = 1
				c = S[i]
		ans += c
		hex = ''
		while count:
			rem = count % 16
			if rem < 10:
				hex += chr(48 + rem)
			else:
				hex += chr(97 + rem - 10)
			count //= 16
		ans += hex
		ans = ans[::-1]
		return ans


class Solution:

	def encryptString(self, S):
		newString = ''
		previousChar = S[0]
		currentChar = S[0]
		charCount = 1
		hexRep = hex(charCount)
		for i in range(1, len(S)):
			currentChar = S[i]
			if currentChar != previousChar:
				newString = newString + previousChar
				hexRep = hex(charCount)
				hexRep = hexRep[2:]
				hexRep = hexRep[::-1]
				newString = newString + hexRep
				previousChar = currentChar
				charCount = 1
			else:
				charCount = charCount + 1
		if charCount > 1:
			newString = newString + previousChar
			hexRep = hex(charCount)
			hexRep = hexRep[2:]
			hexRep = hexRep[::-1]
			newString = newString + hexRep
		else:
			newString = newString + previousChar
			hexRep = hex(charCount)
			hexRep = hexRep[2:]
			hexRep = hexRep[::-1]
			newString = newString + hexRep
		result = newString[::-1]
		return result


class Solution:

	def encryptString(self, S):
		(count, temp, result) = (0, [], '')
		for i in range(len(S)):
			if i < len(S) - 1 and S[i] == S[i + 1]:
				count += 1
			else:
				temp.append(str(hex(count + 1))[2:] + S[i])
				count = 0
		for j in range(len(temp) - 1, -1, -1):
			result += temp[j]
		return result


class Solution:

	def encryptString(self, S):
		cnt = 1
		ans = []
		for i in range(1, len(S)):
			if S[i] == S[i - 1]:
				cnt += 1
				continue
			else:
				ans.append(S[i - 1])
				ans.append(hex(cnt)[2:])
				cnt = 1
		ans.append(S[-1])
		ans.append(hex(cnt)[2:])
		ans = ans[::-1]
		encrypt = ''.join(ans)
		return encrypt


class Solution:

	def encryptString(self, S):
		temp = []
		count = 1
		for i in range(len(S)):
			if i < len(S) - 1 and S[i] == S[i + 1]:
				count += 1
			else:
				temp.append(str(hex(count)[2:]) + S[i])
				count = 1
		temp.reverse()
		return ''.join(temp)


class Solution:

	def encryptString(self, S):
		new_string = S[0]
		count = 1
		for i in range(1, len(S)):
			if S[i] == S[i - 1]:
				count += 1
			else:
				new_string += str(hex(count)[2:])[::-1]
				new_string += S[i]
				count = 1
		new_string += str(hex(count)[2:])[::-1]
		new_string = new_string[::-1]
		return new_string


class Solution:

	def encryptString(self, S):
		count = 1
		ans = []
		for i in range(len(S) - 1):
			if S[i] == S[i + 1]:
				count += 1
			else:
				ans.extend([S[i], hex(count)[2:]])
				count = 1
		if count:
			ans.extend([S[-1], hex(count)[2:]])
		ans = ans[::-1]
		return ''.join(ans)


class Solution:

	def convertToHex(self, num):
		temp = ''
		while num != 0:
			rem = num % 16
			c = 0
			if rem < 10:
				c = rem + 48
			else:
				c = rem + 87
			temp += chr(c)
			num = num // 16
		return temp

	def encryptString(self, S):
		n = len(S)
		ans = ''
		i = 0
		while i < n:
			ch = S[i]
			count = 0
			while i < n and S[i] == ch:
				count += 1
				i += 1
			hex = self.convertToHex(count)
			ans += ch
			ans += hex
		ans = ans[::-1]
		return ans


class Solution:

	def convert(num):
		ans = ''
		while num != 0:
			rem = num % 16
			d = 0
			if rem < 10:
				d = rem + 48
			else:
				d = rem + 87
			ans += chr(d)
			num = num // 16
		return ans

	def encryptString(self, S):
		res = ''
		n = len(S)
		i = 0
		while i < n:
			s = S[i]
			c = 0
			while i < n and S[i] == s:
				c += 1
				i += 1
			hexa = Solution.convert(c)
			res += s
			res += hexa
		res = res[::-1]
		return res


class Solution:

	def encryptString(self, S):
		start = 0
		end = 0
		final = ''
		for i in range(0, len(S)):
			if S[i] == S[start]:
				end = i
			else:
				final = '{0:x}'.format(end - start + 1) + S[start] + final
				start = i
				end = i
		final = '{0:x}'.format(end - start + 1) + S[start] + final
		return final


class Solution:

	def encryptString(self, S):
		d = {10: 'a', 11: 'b', 12: 'c', 13: 'd', 14: 'e', 15: 'f'}
		result = ''
		count = 1
		for i in range(1, len(S)):
			if S[i] == S[i - 1]:
				count += 1
			else:
				result = str(hex(count))[2:] + S[i - 1] + result
				count = 1
		result = str(hex(count))[2:] + S[-1:] + result
		return result


class Solution:

	def generateHex(self, num):
		temp = ''
		while num != 0:
			rem = num % 16
			count = 0
			count = rem + (48 if rem < 10 else 87)
			temp += chr(count)
			num //= 16
		return temp

	def encryptString(self, S):
		d = {10: 'a', 11: 'b', 12: 'c', 13: 'd', 14: 'e', 15: 'f'}
		i = 0
		ans = ''
		n = len(S)
		while i < n:
			ch = S[i]
			chrCount = 0
			while i < n and S[i] == ch:
				chrCount += 1
				i += 1
			ans += ch + self.generateHex(chrCount)
		ans = ans[::-1]
		return ans


class Solution:

	def encryptString(self, S):
		res = []
		temp = S[0]
		count = 1
		str1 = ''
		for i in range(1, len(S)):
			if S[i] != temp:
				a = str(hex(count))
				a = a.replace('0x', '')
				res.append(temp)
				res.append(a)
				temp = S[i]
				count = 1
			else:
				count += 1
		a = str(hex(count))
		a = a.replace('0x', '')
		res.append(temp)
		res.append(a)
		return str1.join(res[::-1])


class Solution:

	def encryptString(self, S):
		res = ''
		i = 0
		while i < len(S) - 1:
			count = 1
			while S[i] == S[i + 1]:
				count += 1
				i += 1
				if i == len(S) - 1:
					break
			res = hex(count)[2:] + S[i] + res
			i += 1
		if S[len(S) - 1] != S[len(S) - 2]:
			res = '1' + S[len(S) - 1] + res
		return res


class DecToHex(object):

	def __init__(self):
		pass

	def dec_to_bin(self, num):
		if num == 0:
			return '0'
		bin_str = ''
		rem = 0
		while num != 0:
			rem = num % 2
			bin_str = str(rem) + bin_str
			num //= 2
		return bin_str

	def bin_to_hex(self, bin_num: str):
		hex_map = {10: 'a', 11: 'b', 12: 'c', 13: 'd', 14: 'e', 15: 'f'}
		hex_str = ''
		tnum = bin_num
		if len(bin_num) % 4 != 0:
			tnum = '0' * (4 - len(bin_num) % 4) + bin_num
		tval = 0
		mul = 1
		for i in range(len(tnum) - 1, -1, -1):
			tval = tval + int(tnum[i]) * mul
			mul = mul * 2
			if i % 4 == 0:
				if tval < 10:
					hex_str = str(tval) + hex_str
				else:
					hex_str = hex_map[tval] + hex_str
				mul = 1
				tval = 0
		return hex_str

	def dec_to_hex(self, num):
		bin_str = self.dec_to_bin(num)
		hex_str = self.bin_to_hex(bin_str)
		return hex_str

	def encryptword(self, word):
		res_str = ''
		prev_letter = word[0]
		cnt = 0
		for i in range(len(word)):
			if prev_letter == word[i]:
				cnt += 1
			else:
				res_str = self.dec_to_hex(cnt) + prev_letter + res_str
				cnt = 1
				prev_letter = word[i]
		res_str = self.dec_to_hex(cnt) + prev_letter + res_str
		return res_str

class Solution:

	def encryptString(self, S):
		dectohex = DecToHex()
		return dectohex.encryptword(S)


class Solution:

	def encryptString(self, S):
		count = 0
		char = S[0]
		string = ''
		for item in S:
			if item == char:
				count += 1
			else:
				string = hex(count)[2:] + char + string
				char = item
				count = 1
		string = hex(count)[2:] + char + string
		return string


class Solution:

	def encryptString(self, S):
		up = S[0]
		ad = 0
		ans = ''
		for mn in range(0, len(S)):
			if S[mn] == up:
				ad += 1
				if mn == len(S) - 1:
					ynu = str(hex(ad))
					uui = ynu[2:]
					olu = list(uui)
					olu.reverse()
					uui = ''.join(olu)
					ans += str(up) + uui
			else:
				ynu = str(hex(ad))
				uui = ynu[2:]
				olu = list(uui)
				olu.reverse()
				uui = ''.join(olu)
				ans += str(up) + uui
				up = S[mn]
				ad = 1
				if mn == len(S) - 1:
					ynu = str(hex(ad))
					uui = ynu[2:]
					ans += str(up) + uui
		vhy = list(ans)
		vhy.reverse()
		lop = ''.join(vhy)
		return lop


class Solution:

	def encryptString(self, S):
		last = None
		count = 0
		result = []
		for ch in S:
			if ch == last:
				count += 1
			else:
				if count > 0:
					result.append('%x%c' % (count, last))
				last = ch
				count = 1
		if count > 0:
			result.append('%x%c' % (count, ch))
		result.reverse()
		return ''.join(result)


class Solution:

	def encryptString(self, S):
		if len(S) == 1:
			return '1' + S
		elif len(S) == 2:
			if S[0] == S[1]:
				return '2' + S[0]
			else:
				return '1' + S[1] + '1' + S[0]
		res = ''
		n = len(S)
		count = 1
		i = 1
		S = S + '$'
		while i < n + 1:
			while i < n + 1 and S[i] == S[i - 1]:
				count += 1
				i += 1
			res = res + S[i - 1] + hex(count)[2:][::-1]
			count = 1
			i += 1
		return res[::-1]


class Solution:

	def encryptString(self, S):
		prev_alpha = None
		count = 0
		apha_num = []
		for i in S:
			if prev_alpha is None or prev_alpha == i:
				prev_alpha = i
				count += 1
			else:
				apha_num.append(prev_alpha)
				apha_num.append(str(hex(count)).replace('0x', ''))
				prev_alpha = i
				count = 1
		apha_num.append(prev_alpha)
		apha_num.append(str(hex(count)).replace('0x', ''))
		return ''.join(apha_num[::-1])


class Solution:

	def reverse(self, s):
		res = ''
		for i in range(len(s) - 1, -1, -1):
			res += s[i]
		return res

	def dec_to_hex(self, n):
		res = ''
		while n > 0:
			r = n % 16
			if r < 10:
				res += chr(ord('0') + r)
			else:
				res += chr(ord('a') + r - 10)
			n = n // 16
		return res

	def encryptString(self, S):
		n = len(S)
		res = ''
		i = 0
		j = 0
		while j < n:
			if S[i] == S[j]:
				j += 1
			else:
				count = j - i
				hex_num = self.dec_to_hex(count)
				res += S[i] + hex_num
				i = j
		count = j - i
		hex_num = self.dec_to_hex(count)
		res += S[i] + hex_num
		res = self.reverse(res)
		return res


class Solution:

	def encryptString(self, S):
		ans = ''
		c = ''
		c += S[-1]
		count = 1
		for i in range(len(S) - 2, -1, -1):
			if S[i] == c[-1]:
				count += 1
			else:
				h = hex(count)[2:]
				ans += h
				ans += c
				c = S[i]
				count = 1
		h = hex(count)[2:]
		ans += h
		ans += c
		return ans


class Solution:

	def encryptString(self, S):
		curr = S[0]
		count = 1
		i = 1
		word = ''
		while i < len(S):
			if S[i] == curr:
				count += 1
			else:
				word = '{0:x}'.format(count) + curr + word
				curr = S[i]
				count = 1
			i += 1
		word = '{0:x}'.format(count) + curr + word
		return word


class Solution:

	def encryptString(self, S):
		count = 0
		res = ''
		current = S[len(S) - 1]
		for i in S[::-1]:
			if i == current:
				count += 1
			else:
				res += hex(count)[2:] + current
				count = 1
				current = i
		res += hex(count)[2:] + current
		return res


class Solution:

	def encryptString(self, S):
		s = S + ' '
		c = 1
		j = 1
		r = ''
		while j < len(s):
			if s[j - 1] == s[j]:
				c += 1
			else:
				r = hex(c)[2:] + s[j - 1] + r
				c = 1
			j += 1
		return r


class Solution:

	def getHaxadecimal(self, dec, d):
		hexa = ''
		while dec != 0:
			rem = dec % 16
			if rem > 9:
				hexa += str(d[rem])
			else:
				hexa += str(rem)
			dec //= 16
		return hexa

	def encryptString(self, S):
		d = {10: 'a', 11: 'b', 12: 'c', 13: 'd', 14: 'e', 15: 'f'}
		n = len(S)
		count = 1
		ans = ''
		for i in range(1, n):
			if S[i] == S[i - 1]:
				count += 1
			else:
				hexa = self.getHaxadecimal(count, d)
				ans += S[i - 1] + hexa
				count = 1
		hexa = self.getHaxadecimal(count, d)
		ans += S[n - 1] + hexa
		ans = ans[::-1]
		return ans


class Solution:

	def encryptString(self, S):
		subString = []
		initial = 0
		for i in range(1, len(S)):
			if S[i - 1] != S[i]:
				subString.append(S[initial:i])
				initial = i
		subString.append(S[initial:])
		print
		res = ''
		for i in subString:
			res = hex(len(i))[2:] + i[0] + res
		return res


class Solution:

	def encryptString(self, S):
		count = 1
		output = []
		for i in range(len(S) - 1):
			if S[i] == S[i + 1]:
				count += 1
			else:
				output.append(S[i])
				output.append(hex(count)[2:])
				count = 1
		output.append(S[-1])
		output.append(hex(count)[2:])
		return ''.join(output[::-1])


from collections import OrderedDict

class Solution:

	def to_hex(self, num):
		hexes = {0: '0', 1: '1', 2: '2', 3: '3', 4: '4', 5: '5', 6: '6', 7: '7', 8: '8', 9: '9', 10: 'a', 11: 'b', 12: 'c', 13: 'd', 14: 'e', 15: 'f'}
		res = ''
		while num > 0:
			res += hexes[num % 16]
			num = num // 16
		return res

	def encryptString(self, string):
		i = 0
		n = len(string)
		c = 0
		ans = ''
		while i < n:
			if i + 1 < n and string[i] == string[i + 1]:
				c += 1
			else:
				c += 1
				h = self.to_hex(c)
				ans += string[i] + h
				c = 0
			i += 1
		return ans[::-1]


class Solution:

	def encryptString(self, S):
		if len(S) == 1:
			return '' + 1 + S
		op = ''
		(prev, prev_cnt) = (0, 1)
		for i in range(1, len(S)):
			if S[prev] == S[i]:
				prev_cnt += 1
			else:
				temp = hex(prev_cnt).lstrip('0x').rstrip('L') + S[prev]
				op = temp + op
				prev = i
				prev_cnt = 1
		temp = hex(prev_cnt).lstrip('0x').rstrip('L') + S[prev]
		op = temp + op
		return op


class Solution:

	def encryptString(self, S):
		s = {}
		for i in range(0, 10):
			s[i] = str(i)
		for i in range(10, 16):
			s[i] = chr(87 + i)
		r = ''
		n = len(S)
		c = 1
		for i in range(len(S) - 1):
			if S[i] == S[i + 1]:
				c += 1
			else:
				r = r + S[i]
				while c != 0:
					p = c % 16
					r = r + s[p]
					c = c // 16
				c = 1
		r = r + S[n - 1]
		while c != 0:
			o = c % 16
			r = r + s[o]
			c = c // 16
		return r[::-1]


class Solution:

	def encryptString(self, S):

		def numberToBase(n, b):
			if n == 0:
				return ['0']
			digits = []
			while n:
				temp = int(n % b)
				if temp == 10:
					s = 'a'
				elif temp == 11:
					s = 'b'
				elif temp == 12:
					s = 'c'
				elif temp == 13:
					s = 'd'
				elif temp == 14:
					s = 'e'
				elif temp == 15:
					s = 'f'
				else:
					s = str(temp)
				digits.append(s)
				n //= b
			return ''.join(digits[::-1])
		s = S[0]
		cnt = 1
		ans = []
		for i in range(1, len(S)):
			if S[i] == S[i - 1]:
				cnt += 1
			else:
				ans.append(numberToBase(cnt, 16) + s)
				s = S[i]
				cnt = 1
		ans.append(numberToBase(cnt, 16) + s)
		return ''.join(ans[::-1])


class Solution:

	def encryptString(self, s):
		list1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'a', 'b', 'c', 'd', 'e', 'f', 'g']
		countlist = []
		charlist = []
		cur = s[0]
		k = ''
		i = 0
		while i < len(s):
			count = 0
			while i < len(s) and s[i] == cur:
				count += 1
				i += 1
			countlist.append(count)
			charlist.append(s[i - 1])
			if i < len(s):
				cur = s[i]
		for i in range(len(charlist) - 1, -1, -1):
			if countlist[i] > 9:
				k += hex(countlist[i])[2:]
			else:
				k += str(countlist[i])
			k += charlist[i]
		return k


class Solution:

	def encryptString(self, S):
		result = ''
		i = 0

		def convert_to_hexa(count):
			hexa_string = '0123456789abcdef'
			result = ''
			while count:
				(count, remainder) = divmod(count, 16)
				result += hexa_string[remainder]
			return result
		while i < len(S):
			current = S[i]
			count = 0
			while i < len(S) and current == S[i]:
				i += 1
				count += 1
			result += current
			hexa_count = convert_to_hexa(count)
			result += hexa_count
		return result[::-1]


class Solution:

	def encryptString(self, S):
		l = []
		c = 0
		res = ''
		for i in range(len(S)):
			if i < len(S) - 1 and S[i] == S[i + 1]:
				c += 1
			else:
				l.append(str(hex(c + 1))[2:] + S[i])
				c = 0
		for j in range(len(l) - 1, -1, -1):
			res += l[j]
		return res


class Solution:

	def encryptString(self, S):
		count = 1
		tmp = ''
		for i in range(1, len(S)):
			if S[i] == S[i - 1]:
				count += 1
			else:
				hx = hex(count)
				tmp = hx[2:] + S[i - 1] + tmp
				count = 1
		tmp = hex(count)[2:] + S[-1] + tmp
		return tmp


from collections import Counter

class Solution:

	def encryptString(self, S):
		cnt = Counter(S)
		ans = []
		i = 0
		n = len(S)
		while i < n:
			j = i
			cnt = 0
			while j < n and S[i] == S[j]:
				cnt += 1
				j += 1
			ans.append(S[i])
			ans.append(cnt)
			i = j
		for i in range(len(ans)):
			if type(ans[i]) == int:
				t = hex(ans[i]).replace('0x', '')
				if t.isalpha():
					t = t.lower()
				ans[i] = t
		return ''.join(ans[::-1])


class Solution:

	def encryptString(self, S):
		res = ''
		elem = S[0]
		S = S + '0'
		c = 1
		n = len(S)
		for i in range(1, n):
			if S[i] == S[i - 1]:
				c += 1
			else:
				h = hex(c)
				res = res + elem + ''.join(reversed(h.lstrip('0x').rstrip('L')))
				c = 1
				elem = S[i]
		return ''.join(reversed(res))


class Solution:

	def encryptString(self, S):
		st = ''
		c = 1
		for i in range(1, len(S)):
			if S[i] == S[i - 1]:
				c += 1
			else:
				st = S[i - 1] + st
				x = hex(c)
				x = x.replace('0x', '')
				st = x + st
				c = 1
		st = S[len(S) - 1] + st
		x = hex(c)
		x = x.replace('0x', '')
		st = x + st
		return st


class Solution:

	def encryptString(self, S):
		output = ''
		previousLetter = S[0]
		count = 1
		for idx in range(1, len(S)):
			if S[idx] == previousLetter:
				count += 1
			else:
				output = str(hex(count).lstrip('0x').rstrip('L')) + previousLetter + output
				previousLetter = S[idx]
				count = 1
		return str(hex(count).lstrip('0x').rstrip('L')) + previousLetter + output


class Solution:

	def int_hex(self, num):
		hex_decimal = {10: 'a', 11: 'b', 12: 'c', 13: 'd', 14: 'e', 15: 'f'}
		res = ''
		while num > 15:
			rem = num % 16
			if rem > 9:
				rem = hex_decimal[rem]
			res = str(rem) + res
			num = num // 16
		if num > 9:
			num = hex_decimal[num]
		return str(num) + res

	def encryptString(self, S):
		res = ''
		c = ''
		cnt = 1
		i = 0
		while i < len(S):
			c = S[i]
			cnt = 1
			i += 1
			while i < len(S) and S[i] == c:
				cnt += 1
				i += 1
			hex_cnt = self.int_hex(cnt)
			res = hex_cnt + c + res
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.encryptString(S))


class Solution:

	def encryptString(self, S):
		res = ''
		i = 0
		while i < len(S) - 1:
			count = 1
			while S[i] == S[i + 1]:
				count += 1
				i += 1
				if i == len(S) - 1:
					break
			res = hex(count)[2:] + S[i] + res
			i += 1
		if S[len(S) - 1] != S[len(S) - 2]:
			res = '1' + S[len(S) - 1] + res
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.encryptString(S))


class Solution:

	def encryptString(self, S):
		ans = ''
		count = 0
		c = S[0]
		count = 1
		for i in range(1, len(S)):
			if S[i] == S[i - 1]:
				count += 1
			else:
				ans += c
				hx = ''
				while count:
					rem = count % 16
					if rem < 10:
						hx += chr(48 + rem)
					else:
						hx += chr(97 + rem - 10)
					count //= 16
				ans += hx
				c = S[i]
				count = 1
		ans += c
		hx = ''
		while count:
			rem = count % 16
			if rem < 10:
				hx += chr(48 + rem)
			else:
				hx += chr(97 + rem - 10)
			count //= 16
		ans += hx
		ans = ans[::-1]
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.encryptString(S))


class Solution:

	def encryptString(self, S):
		display_char = S[0]
		curr_count = 0
		l1 = []
		for i in range(len(S)):
			if S[i] == display_char:
				curr_count += 1
			else:
				hex_value = hex(curr_count)[2:]
				l1.append(display_char)
				l1.append(hex_value)
				display_char = S[i]
				curr_count = 1
		else:
			hex_value = hex(curr_count)[2:]
			l1.append(display_char)
			l1.append(hex_value)
		l1.reverse()
		ans = ''.join(l1)
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.encryptString(S))


class Solution:

	def encryptString(self, S):

		def sth(num):
			temp = ''
			while num != 0:
				rem = num % 16
				c = 0
				if rem < 10:
					c = rem + 48
				else:
					c = rem + 87
				temp += chr(c)
				num = num // 16
			return temp

		def en(S):
			i = 0
			ans = ''
			n = len(S)
			while i < n:
				count = 0
				chr = S[i]
				while i < n and S[i] == chr:
					count += 1
					i += 1
				a = sth(count)
				ans += chr
				ans += a
			ans = ans[::-1]
			return ans
		b = en(S)
		return b


class Solution:

	def encryptString(self, s):
		if len(s) == 1:
			return '1' + s[0]
		c = 1
		t = []
		for i in range(len(s) - 1):
			if s[i] == s[i + 1]:
				c += 1
			else:
				t.extend([s[i], hex(c)[2:]])
				c = 1
			if i == len(s) - 2:
				t.extend([s[i + 1], hex(c)[2:]])
		t = t[::-1]
		return ''.join(t)