Given a string S that consists of only alphanumeric characters and dashes. The string is separated into N + 1 groups by N dashes. Also given an integer K. 
We want to reformat the string S, such that each group contains exactly K characters, except for the first group, which could be shorter than K but still must contain at least one character. Furthermore, there must be a dash inserted between two groups, and you should convert all lowercase letters to uppercase.
Return the reformatted string.
Example 1:
Input: 
S = "5F3Z-2e-9-w", K = 4
Output: "5F3Z-2E9W"
Explanation: The string S has been split into two
parts, each part has 4 characters. Note that two
extra dashes are not needed and can be removed.
Example 2:
Input:
S = "2-5g-3-J", K = 2
Output: "2-5G-3J"
Explanation: The string s has been split 
into three parts, each part has 2 characters 
except the first part as it could
be shorter as mentioned above.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function ReFormatString() which takes a string S and an integer K as input and returns the reformatted string.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ S.length() ≤ 10^{5}
1 ≤ K ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def ReFormatString(self,S, K):

        #code here

Solutions:
class Solution:

	def ReFormatString(self, S, K):
		c = K
		N = len(S)
		size = 0
		ans = []
		for j in range(N - 1, -1, -1):
			tmp = S[j]
			if tmp >= 'a' and tmp <= 'z':
				tmp = chr(65 + (ord(tmp) - 97))
			if S[j] != '-' and c:
				ans.append(tmp)
				c -= 1
				size += 1
			elif c == 0:
				c = K
				ans.append('-')
				size += 1
				if S[j] != '-':
					ans.append(tmp)
					c -= 1
					size += 1
		if size == 0:
			return ''
		if ans[size - 1] == '-':
			ans.pop()
		ans = ans[::-1]
		return ''.join(ans)


class Solution:

	def ReFormatString(self, S, K):
		temp = ''
		n = len(s)
		for i in range(0, n):
			if s[i] != '-':
				temp += s[i].upper()
		length = len(temp)
		ans = ''
		val = k
		for i in range(length - 1, -1, -1):
			if val == 0:
				val = k
				ans += '-'
			ans += temp[i]
			val -= 1
		ans = ans[::-1]
		return ans


from collections import deque

class Solution:

	def ReFormatString(self, S, K):
		s = deque()
		cnt = 0
		for i in range(len(S) - 1, -1, -1):
			if S[i] != '-':
				s.appendleft(S[i].upper())
				cnt += 1
				if cnt == K:
					s.appendleft('-')
					cnt = 0
		return ''.join(s).lstrip('-')


class Solution:

	def ReFormatString(self, S, K):
		S_l = S.split('-')
		S_j = ''.join(S_l)
		len_s = len(S_j)
		word_list = []
		i = len_s
		while i > 0:
			if i - K >= 0:
				word = S_j[i - K:i]
			else:
				word = S_j[:i]
			word_list.append(word)
			i = i - K
		word_list = word_list[::-1]
		final_word = '-'.join(word_list)
		return final_word.upper()


class Solution:

	def ReFormatString(self, S, K):
		l = ''.join(list(S.split('-')))
		s = ''
		c = 0
		for i in range(len(l) - 1, -1, -1):
			if c == K - 1:
				s += l[i].upper() + '-'
				c = 0
			else:
				s += l[i].upper()
				c += 1
		if s.endswith('-') == True:
			return s[:-1][::-1]
		else:
			return s[::-1]


class Solution:

	def ReFormatString(self, S, K):
		li = []
		S = S.replace('-', '')
		if K >= len(S):
			return S.upper()
		j = 0
		for i in range(len(S) % K):
			if S[j] != '-':
				li.append(S[j].upper())
			j += 1
		if len(S) % K != 0:
			li.append('-')
		while j < len(S):
			i = 0
			while i < K:
				if S[j] != '-':
					li.append(S[j].upper())
					i += 1
				j += 1
			li.append('-')
		li.pop()
		return ''.join(li)


class Solution:

	def ReFormatString(self, S, K):
		s = S.replace('-', '')
		out = ''
		count = 0
		for idx in range(len(s) - 1, -1, -1):
			if count % K == 0 and count != 0:
				out += '-'
				count = 0
			out += s[idx].upper()
			count += 1
		return out[::-1]


class Solution:

	def ReFormatString(self, s, K):
		a = ''
		l = len(s)
		for i in range(0, l):
			if s[i] <= 'Z' and s[i] >= 'A':
				a = a + s[i]
			elif s[i] != '-':
				a = a + s[i].upper()
		b = ''
		l = len(a)
		t = 0
		while t < l:
			if t == 0:
				if l % k:
					r = l % k
				else:
					r = k
				b = b + a[t:r]
				b = b + '-'
				t = r
			else:
				b = b + a[t:t + K] + '-'
				t = t + k
		return b[0:len(b) - 1]


class Solution:

	def ReFormatString(self, S, K):
		a = []
		for i in range(len(S)):
			if S[i] != '-':
				a.append(S[i])
		k = len(a) // K
		r = len(a) % K
		ans = ''
		for i in range(r):
			ans += a[i].upper()
		for i in range(k):
			if len(ans) > 0:
				ans += '-'
			for j in range(i * K + r, i * K + K + r):
				ans += a[j].upper()
		return ans


class Solution:

	def ReFormatString(self, S, K):
		S = S.upper()
		l = 0
		for i in range(len(S)):
			if S[i] != '-':
				l += 1
		equal_parts = l // K
		first_part_len = l % K
		res = ''
		i = 0
		while len(res) < first_part_len:
			if S[i] != '-':
				res += S[i]
			i += 1
		if res != '' and equal_parts:
			res += '-'
		checker = 0
		for j in range(i, len(S)):
			if S[j] != '-':
				res += S[j]
				checker += 1
			if checker == K:
				equal_parts -= 1
				checker = 0
				if equal_parts:
					res += '-'
		return res


class Solution:

	def ReFormatString(self, S, K):
		r = []
		for i in S:
			if i != '-':
				r.append(i.upper())
		p = len(r) % k
		res = ''
		if p != 0:
			res += ''.join(r[:p])
			res += '-'
		for i in range(max(len(res) - 1, 0), len(S), k):
			res += ''.join(r[i:i + K])
			res += '-'
		j = len(res) - 1
		while j >= 0:
			if res[j] != '-':
				break
			j -= 1
		return res[:j + 1]


from collections import deque

class Solution:

	def ReFormatString(self, S, K):
		dq = deque()
		res = ''
		cnt = 0
		for i in range(len(S) - 1, -1, -1):
			if S[i] == '-':
				continue
			dq.appendleft(S[i])
			cnt += 1
			if cnt == K:
				cnt = 0
				dq.appendleft('-')
		if len(dq) == 0:
			return res
		res += dq.popleft()
		if res == '-':
			res = ''
		while dq:
			res += dq.popleft()
		return res.upper()


class Solution:

	def ReFormatString(self, S, K):
		arr = S.split('-')
		arr1 = ''.join(arr)
		str1 = ''
		m = len(arr1) % K
		str1 = ''
		if m != 0:
			str1 = arr1[:m] + '-'
		for i in range(m, len(arr1), k):
			str1 += arr1[i:i + k] + '-'
		return str1[:len(str1) - 1].upper()


class Solution:

	def ReFormatString(self, S, K):
		s2 = ''
		for i in S[::-1]:
			if i != '-':
				if len(s2) % (K + 1) == K:
					s2 += '-'
				s2 += i.upper()
		return s2[::-1]


class Solution:

	def ReFormatString(self, S, K):
		ans = ''
		X = ''
		count = 0
		for i in range(len(S) - 1, -1, -1):
			if S[i] != '-':
				X += str.upper(S[i])
				count += 1
			if count == K:
				ans += X + '-'
				count = 0
				X = ''
		if count != 0:
			ans += X
		if len(ans) == 0:
			return ''
		if ans[-1] == '-':
			n = len(ans)
			return ans[:n - 1][::-1]
		return ans[::-1]


class Solution:

	def ReFormatString(self, S, K):
		string = S.split('-')
		length = 0
		newString = ''
		for i in range(len(string)):
			length += len(string[i])
			newString += string[i]
		newString = newString.upper()
		result = ''
		firststr = length % K
		result += newString[:firststr]
		for i in range(int(length / K)):
			result += '-' + newString[firststr + i * K:firststr + i * K + K]
		if firststr:
			return result
		else:
			return result[1:]


class Solution:

	def ReFormatString(self, S, k):
		ans = ''
		n = len(S)
		cnt = 0
		for i in range(n - 1, -1, -1):
			if S[i] == '-':
				continue
			else:
				cnt += 1
				if cnt == k:
					ans += S[i].upper()
					ans += '-'
					cnt = 0
				else:
					ans += S[i].upper()
		if not ans:
			return ''
		ans = ans[::-1]
		if ans[0] == '-':
			return ans[1:]
		return ans


class Solution:

	def ReFormatString(self, S, K):
		S = S.upper()
		parts = ''.join(S.split('-'))[::-1]
		final_parts = []
		i = 0
		while i < len(parts):
			final_parts.append(parts[i:i + k][::-1])
			i += k
		final_parts.reverse()
		return '-'.join(final_parts)


class Solution:

	def ReFormatString(self, S, K):
		c = 0
		if len(S) == 1 and S == '-':
			return ''
		ans = ''
		for i in range(len(S) - 1, -1, -1):
			if len(ans) != K and S[i] != '-':
				c += 1
				ans += S[i].upper()
				if c == K:
					c = 0
					ans += '-'
		fin = ans[::-1]
		if fin[0] == '-':
			return fin[1:]
		else:
			return ans[::-1]


class Solution:

	def ReFormatString(self, S, K):
		if len(S) == 1 and S[0] == '-':
			return ''
		elif len(S) == 1:
			return S.upper()
		count = 0
		new_string = ''
		for i in range(len(S) - 1, -1, -1):
			if S[i].isalnum() and s[i] != '-':
				new_string += S[i].upper()
				count += 1
				if count == K:
					new_string += '-'
					count = 0
		my_string = new_string[::-1]
		if my_string[0] == '-':
			return my_string[1:]
		return my_string[:]


class Solution:

	def ReFormatString(self, S, K):
		c = 0
		ans = ''
		for i in range(len(s) - 1, -1, -1):
			if s[i] == '-':
				continue
			elif c < K:
				c = c + 1
				ans = ans + s[i].upper()
			else:
				c = 1
				ans = ans + '-'
				ans = ans + s[i].upper()
		m = ans[::-1]
		return m


class Solution:

	def ReFormatString(self, S, K):
		res = ''
		d = 0
		for i in range(len(S) - 1, -1, -1):
			if S[i] == '-':
				continue
			if d >= K:
				res += '-'
				res += S[i].upper()
				d = 1
			else:
				res += S[i].upper()
				d += 1
		return res[::-1]


class Solution:

	def ReFormatString(self, S, K):
		S = S.upper()
		output = []
		i = 0
		j = 0
		for i in range(len(S)):
			if S[-i - 1] != '-':
				output.append(S[-i - 1])
				j += 1
				if not j % K:
					output.append('-')
		if output and output[-1] == '-':
			output.pop()
		return ''.join(reversed(output))


class Solution:

	def ReFormatString(self, S, K):
		val = K
		l = len(S)
		temp = ''
		for i in range(l):
			if S[i] != '-':
				temp += S[i].upper()
		temp_l = len(temp)
		ans = ''
		for i in range(temp_l - 1, -1, -1):
			while val == 0:
				val = k
				ans += '-'
			ans += temp[i]
			val -= 1
		ans = ans[::-1]
		return ans


class Solution:

	def ReFormatString(self, S, K):
		S = S.replace('-', '').upper()
		if len(S) <= K:
			return S
		first_group_length = len(S) % K
		output = S[:first_group_length]
		for i in range(first_group_length, len(S), K):
			output += '-' + S[i:i + K]
		if first_group_length == 0:
			return output[1:]
		else:
			return output


class Solution:

	def ReFormatString(self, S, K):
		S = S.upper()
		l = S.split('-')
		sen = ''
		for i in l:
			sen = sen + i
		ans = ''
		val = 0
		if len(sen) > K:
			if len(sen) % K == 0:
				val = K
			else:
				val = len(sen) % K
			ans = ans + sen[:val]
			ans = ans + '-'
		elif len(l[0]) == 0 and len(sen) <= K:
			ans = ans + sen[:len(sen)]
			return ans
		index = val
		while index < len(sen):
			count = 0
			while count < K and index < len(sen):
				ans = ans + sen[index]
				count += 1
				index += 1
			if index < len(sen):
				ans = ans + '-'
		return ans


class Solution:

	def ReFormatString(self, S, K):
		S = S.upper()
		l = len(S)
		c = 0
		W = ''
		w = ''
		for i in range(l - 1, -1, -1):
			if S[i] != '-':
				w = w + S[i]
				c = c + 1
			if i > 0 and c == K:
				W = W + w + '-'
				c = 0
				w = ''
			elif i == 0:
				W = W + w
		rev = W[::-1]
		l = len(rev)
		if len(rev) > 0 and rev[0] == '-':
			return rev[1:]
		return rev


class Solution:

	def ReFormatString(self, S, K):
		s = ''
		count = 0
		for i in range(len(S) - 1, -1, -1):
			if S[i] == '-':
				continue
			if count == K:
				s += '-'
				count = 0
			s += S[i].upper()
			count += 1
		return s[::-1]


class Solution:

	def ReFormatString(self, S, K):
		S = S.upper()
		S = S.replace('-', '')
		S = S[::-1]
		res = []
		for i in range(0, len(S), K):
			res.append(S[i:i + K])
		return '-'.join(res)[::-1]


class Solution:

	def ReFormatString(self, S, K):
		new_s = ''
		for i in S:
			if i != '-':
				new_s += i
		new_s = new_s.upper()
		first_g = len(new_s) % K
		if K >= len(new_s):
			return new_s
		cnt = 0
		if first_g:
			new_s = new_s[0:first_g] + '-' + new_s[first_g:]
			cnt = 1
		temp = 0
		last_g = len(new_s)
		if cnt:
			last_g = len(new_s) - 1
		for i in range(first_g, last_g):
			if temp == K:
				new_s = new_s[:i + cnt] + '-' + new_s[i + cnt:]
				temp = 0
				cnt += 1
			temp += 1
		return new_s


class Solution:

	def ReFormatString(self, S, K):
		final_string = ''
		S = S.replace('-', '')
		prev_index = len(S)
		range1 = 0
		if len(S) % K == 0:
			range1 = len(S) // K
		else:
			range1 = len(S) // K + 1
		for i in range(range1):
			index = -K
			final_string = S[index:] + '-' + final_string
			S = S[:index]
			prev_index = index
		return final_string.upper()[:-1]


class Solution:

	def ReFormatString(self, S, k):
		res = ''
		count = 0
		for i in range(len(S) - 1, -1, -1):
			if S[i] == '-':
				continue
			ch = S[i]
			if ch.isalpha():
				ch = ch.upper()
			if count < k:
				res += ch
				count += 1
			else:
				res += '-'
				res += ch
				count = 1
		res = res[::-1]
		return res


import collections

class Solution:

	def ReFormatString(self, S, K):
		s = ''
		j = 0
		for i in range(len(S) - 1, -1, -1):
			if S[i] != '-':
				if j == K:
					s += '-'
					j = 0
				s += S[i].upper()
				j += 1
		return s[::-1]


class Solution:

	def ReFormatString(self, S, K):
		str = S.replace('-', '').upper()
		if K >= len(str):
			return str
		else:
			ans = ''
			if len(str) % K == 0:
				ans += str[0:K - 1]
				for i in range(K - 1, len(str)):
					if (i + 1) % K != 0:
						ans += str[i]
					else:
						ans += str[i] + '-'
				return ans[:len(ans) - 1]
			else:
				num = len(str) % K
				ans += str[:num] + '-'
				j = 1
				for i in range(num, len(str)):
					if j % K != 0:
						ans += str[i]
						j += 1
					else:
						ans += str[i] + '-'
						j = 1
				return ans[:len(ans) - 1]


class Solution:

	def ReFormatString(self, S, K):
		i = len(S) - 1
		count = K
		res = ''
		while i >= 0:
			if ord(S[i]) == 45:
				i -= 1
				continue
			if ord(S[i]) >= 97:
				res += chr(65 + (ord(S[i]) - 97))
			else:
				res += S[i]
			count -= 1
			if count == 0:
				count = K
				res += '-'
			i -= 1
		res = res[::-1]
		if len(res) > 0 and res[0] == '-':
			return res[1:]
		return res


class Solution:

	def ReFormatString(self, S, K):
		b = ''
		c = ''
		for i in S:
			if i.isalnum():
				b += i
		b = b.upper()
		b = list(b)
		for j in range(len(b) - K, 0, -K):
			b.insert(j, '-')
		for i in b:
			c += i
		return c


class Solution:

	def ReFormatString(self, S, K):
		if not S:
			return ''
		s = ''.join(S.split('-'))
		n = len(s)
		i = n - 1
		counter = 0
		res = []
		x = ''
		while i >= 0:
			if counter == K:
				res.append(x)
				x = ''
				counter = 0
			if not s[i].isdigit() and s[i].islower():
				x = s[i].upper() + x
			else:
				x = s[i] + x
			counter += 1
			i -= 1
		res.append(x)
		return '-'.join(reversed(res))


class Solution:

	def ReFormatString(self, S, K):
		output = S.replace('-', '')
		output = output.upper()
		counter = 0
		for i in range(len(output) - 1, -1, -1):
			counter += 1
			if counter >= K and i != 0:
				counter = 0
				output = output[0:i] + '-' + output[i:len(output)]
		return output


class Solution:

	def ReFormatString(self, S, K):
		new = ''
		for i in S:
			if i != '-':
				new += i.upper()
		if len(new) <= K:
			return new
		l = len(new)
		new2 = new[l - k:l]
		l = l - K
		while l - K >= 0:
			new2 = new[l - k:l] + '-' + new2
			l = l - K
		if l > 0:
			new2 = new[:l] + '-' + new2
		return new2


class Solution:

	def ReFormatString(self, S, K):
		sArr = S.split('-')
		newS = ''.join(sArr)
		newArr = []
		count = len(newS)
		while count > 0:
			if count - k < 0:
				newArr.append(newS[0:count])
			else:
				newArr.append(newS[count - K:count])
			count -= K
		ans = '-'.join(newArr[::-1])
		return ans.upper()


class Solution:

	def ReFormatString(self, S, K):
		S = ''.join(S.split('-')).upper()
		n = len(S) % K
		N = len(S) // K
		strings = []
		if n != 0:
			strings.append(S[:n])
		for i in range(N):
			strings.append(S[n + K * i:n + K * (i + 1)])
		return '-'.join(strings)


class Solution:

	def ReFormatString(self, S, K):
		lst = S.split('-')
		totalString = ''.join(lst)
		totalString = totalString.upper()
		n = len(totalString)
		length = n // K
		j = n % K
		if j == 0:
			j = K
		res = totalString[:j]
		while j < n:
			res += '-'
			res += totalString[j:j + K]
			j += K
		return res


class Solution:

	def ReFormatString(self, S, K):
		a = list(S.split('-'))
		s = ''
		for i in a:
			s += i
		s = s.upper()
		m = len(s) % K
		if m == 0:
			m = K
		res = s[:m]
		while m < len(s):
			res = res + '-' + s[m:m + K]
			m += k
		return res


class Solution:

	def ReFormatString(self, S, K):
		(ans, count) = ([], 0)
		for i in range(len(S) - 1, -1, -1):
			if S[i] != '-':
				ans.append(S[i].upper())
				count += 1
				if count % K == 0:
					ans.append('-')
		if len(ans) > 0 and ans[-1] == '-':
			ans.pop()
		ans.reverse()
		return ''.join(ans)


class Solution:

	def ReFormatString(self, S, K):
		x = ''
		for i in S:
			if i != '-':
				x += i
		x = x.upper()
		ans = ''
		for i in range(len(x) % K):
			ans += x[i]
		for i in range(len(x) % K, len(x)):
			if i % K == len(x) % K and i != len(x) and (i != 0):
				ans += '-'
			ans += x[i]
		return ans


class Solution:

	def ReFormatString(self, string, k):
		ans = ''
		s = string.replace('-', '')
		n = len(s)
		mod = n % k
		c = 0
		if mod != 0:
			ans = s[0:mod] + '-'
		for i in range(mod, n):
			ans += s[i]
			c += 1
			if c == k:
				ans += '-'
				c = 0
		return ans[0:len(ans) - 1].upper()


class Solution:

	def ReFormatString(self, S, K):
		if s == '-':
			return ''
		a = [i for i in S if i != '-']
		for i in range(len(a)):
			if a[i].isalpha():
				a[i] = a[i].upper()
		a = ''.join(a)
		n = len(a) % K
		prefix = a[:n]
		i = n
		ans = [prefix]
		while i < len(S):
			if a[i:min(len(a), i + k)] != '':
				ans.append(a[i:min(len(a), i + K)])
			i = i + K
		res = ans[0]
		for i in range(1, len(ans)):
			res += '-' + ans[i]
		if res[0] == '-':
			res = res[1:]
		if res[-1] == '-':
			res = res[:-1]
		return res


class Solution:

	def ReFormatString(self, S, K):
		S = S.replace('-', '', S.count('-'))
		l = len(S)
		while l > K:
			l = l - K
			S = S[:l] + '-' + S[l:]
		return S.upper()


class Solution:

	def ReFormatString(self, S, K):
		z = S.replace('-', '')
		z = z.upper()
		z = ''.join(reversed(z))
		f = []
		while len(z) >= 1:
			f.append(z[0:K])
			f.append('-')
			z = z[K:]
		z = ''.join(f)
		z = ''.join(reversed(z))
		return z[1:]


class Solution:

	def ReFormatString(self, S, K):
		S = S.replace('-', '')
		S = S.upper()
		n = len(S)
		t = n % k
		out = S[0:t]
		for i in range(0, int(n / k)):
			out = out + '-' + S[t:t + k]
			t = t + k
		if len(out) >= 1:
			if out[0] == '-':
				out = out[1:]
		return out


class Solution:

	def ReFormatString(self, S, K):
		st = ''
		(N, k) = (len(S), 0)
		for i in range(N - 1, -1, -1):
			if S[i] == '-':
				continue
			st += S[i].upper()
			k += 1
			if k == K:
				if i != 0:
					st += '-'
				k = 0
		st = st[::-1]
		if st and st[0] == '-':
			return st[1:]
		return st


class Solution:

	def ReFormatString(self, S, K):
		arr = S.split('-')
		s = ''.join(arr)
		s = s.upper()
		res = ''
		for i in range(len(s), 0, -K):
			res = '-' + s[max(0, i - K):i] + res
		return res[1:]


class Solution:

	def ReFormatString(self, S, K):
		S = S.upper()
		op = ''
		sep = '-'
		tK = K
		tOP = ''
		for i in range(len(S) - 1, -1, -1):
			ch = S[i]
			if ch != '-':
				tOP = ch + tOP
				tK -= 1
				if tK == 0:
					if op == '':
						op = tOP
					else:
						op = tOP + sep + op
					tOP = ''
					tK = K
		if len(tOP) > 0:
			if op == '':
				op = tOP
			else:
				op = tOP + sep + op
		return op


class Solution:

	def ReFormatString(self, S, K):
		s = ''.join(S.split('-'))
		n = len(s)
		num = n // K
		rem = n % K
		if rem != 0:
			ans = s[:rem].upper() + '-'
		else:
			ans = ''
		for i in range(rem, n, K):
			ans += s[i:i + K].upper() + '-'
		return ans[:len(ans) - 1]


class Solution:

	def ReFormatString(self, S, K):
		str = ''
		i = 0
		while i < len(S):
			if S[i] != '-':
				if ord(S[i]) > 96:
					str = str + chr(ord(S[i]) - 32)
					i = i + 1
				else:
					str = str + S[i]
					i = i + 1
			else:
				i = i + 1
		s = ''
		i = len(str)
		while i > 0:
			if i > K:
				st = str[i - K:i]
				s = '-' + st + s
				i = i - K
			else:
				s = str[0:i] + s
				i = 0
		return s


class Solution:

	def ReFormatString(self, S, K):
		res = []
		cnt = 0
		for i in range(len(S) - 1, -1, -1):
			if S[i] != '-':
				res.append(S[i].upper())
				cnt += 1
				if cnt == K:
					cnt = 0
					res.append('-')
		if len(res) and res[-1] == '-':
			res.pop()
		res = res[::-1]
		res = ''.join(res)
		return res


class Solution:

	def ReFormatString(self, S, K):
		res = S.upper().split('-')
		res = ''.join(res)
		for i in range(len(res) - K, 0, -K):
			res = res[:i] + '-' + res[i:]
		return res


class Solution:

	def ReFormatString(self, S, K):
		m = ''
		for i in S:
			if i == '-':
				continue
			else:
				m += i
		rev = m[::-1]
		new = ''
		while rev:
			new = new + rev[:K] + '-'
			rev = rev[K:]
		return new[:-1][::-1].upper()


class Solution:

	def ReFormatString(self, S, K):
		letters = []
		for i in S:
			if i != '-':
				letters.append(i.upper())
		i = len(letters) - 1
		ans = []
		count = 0
		times = len(letters) // k
		cur = ''
		while count != times:
			for j in range(k):
				cur += letters[i]
				i -= 1
			ans.append(''.join(reversed(cur)))
			cur = ''
			count += 1
		cur = ''
		if len(letters) % k != 0:
			for i in range(len(letters) % k):
				cur += letters[i]
			ans.append(cur)
		ans.reverse()
		return '-'.join(ans)


class Solution:

	def ReFormatString(self, S, K):
		(a, j) = (0, 0)
		c = []
		d = ''
		for i in range(len(S) - 1, -1, -1):
			if S[i] != '-':
				d += S[i].upper()
				a += 1
			if a == K:
				c.append(d[::-1])
				a = 0
				d = ''
		if a < K and a != 0:
			c.append(d[::-1])
		c = c[::-1]
		return '-'.join(c)


class Solution:

	def ReFormatString(self, S, K):
		alphanstr = []
		for i in S:
			if i.isalpha():
				alphanstr.append(i.upper())
			elif i == '-':
				continue
			else:
				alphanstr.append(i)
		i = len(alphanstr) - K
		while i > 0:
			alphanstr.insert(i, '-')
			i -= K
		return ''.join(alphanstr)


class Solution:

	def ReFormatString(self, S, K):
		if S == '-':
			return ''
		temp = ''.join(reversed(S))
		ans = str()
		current = 0
		for char in temp:
			if char == '-':
				continue
			else:
				ans += char.upper()
				current += 1
				if current == K:
					ans += '-'
					current = 0
		if ans[-1] == '-':
			ans = ans[:-1]
		return ''.join(reversed(ans))


class Solution:

	def combine(self, K, t, l, l1):
		a = 0
		b = K
		for i in range(t):
			l1.extend(l[a:b])
			a = b
			b = b + K
			if i != t - 1:
				l1.append('-')
		return ''.join(l1)

	def ReFormatString(self, S, K):
		s = ''
		l1 = []
		l = S.split('-')
		l = ''.join(l)
		l = [i for i in l]
		j = 0
		for i in l:
			if i.isalpha():
				l[j] = i.upper()
			j = j + 1
		l = ''.join(l)
		r = len(''.join(l)) % K
		t = len(''.join(l)) // K
		if r != 0:
			l1.extend(l[:r])
			if t > 0:
				l1.append('-')
				a = self.combine(K, t, l[r:], l1)
			else:
				a = ''.join(l1)
			return a
		else:
			b = self.combine(K, t, l, l1)
			return b


class Solution:

	def ReFormatString(self, S, K):
		S = S.replace('-', '')
		S = S.upper()
		arr = list(S)
		arr2 = []
		z = 0
		for i in reversed(arr):
			if z == K:
				arr2.append('-')
				z = 0
			arr2.append(i)
			z = z + 1
		return ''.join((str(f) for f in arr2))[::-1]


class Solution:

	def ReFormatString(self, S, K):
		L = []
		s = S.split('-')
		for i in s:
			for j in i:
				L.append(j)
		n = len(L)
		L = L[::-1]
		c = 0
		for i in range(1, n + 1):
			if i % k == 0:
				L.insert(i + c, '-')
				c = c + 1
		L = L[::-1]
		str = ''
		for i in range(len(L)):
			if i == 0 and L[i] == '-':
				continue
			str += L[i]
		str = str.upper()
		return str


class Solution:

	def ReFormatString(self, S, K):
		S = S.replace('-', '')
		S = S.upper()
		new = ''
		count = 0
		for i in range(len(S) - 1, -1, -1):
			new += S[i]
			count += 1
			if count == K and i > 0:
				new += '-'
				count = 0
		return new[::-1]


class Solution:

	def ReFormatString(self, S, K):
		con = K
		str = S.upper()
		rev = str[::-1]
		str_arr = rev.split('-')
		nodash_str = ''.join(str_arr)
		new = ''
		for i in range(len(nodash_str)):
			if i != K:
				new += nodash_str[i]
			else:
				new += '-'
				new += nodash_str[i]
				K = con + K
		return new[::-1]


class Solution:

	def ReFormatString(self, S, K):
		filtered_s = S.replace('-', '')
		filtered_s_cap = filtered_s.upper()
		rev_str = filtered_s_cap[::-1]
		full_len = len(rev_str)
		format_s = ''
		if len(filtered_s_cap) < K:
			return filtered_s_cap
		else:
			for x in range(full_len // K):
				start_str = K * x
				end_str = start_str + K
				format_s += rev_str[start_str:end_str] + '-'
			if full_len % K == 0:
				format_s = format_s[0:-1]
			else:
				format_s += rev_str[end_str:]
			return format_s[::-1]