Skip to content

Instantly share code, notes, and snippets.

@tahia-khan tahia-khan/tc_ab.py
Last active May 15, 2016

Embed
What would you like to do?
def swap(S, i1, i2):
l = list(S)
l[i1], l[i2] = l[i2], l[i1]
S = ''.join(l)
return S
def prependBs(S, N):
nBs = N - len(S)
return "B"*nBs + S
def createString(N, K):
S = ""
lA = 0
rB = 0
if K == 0:
return prependBs(S, N)
elif K == 1 and N >= 2:
S = "AB"
return prependBs(S, N)
else:
# the upper limit of pairs will be the approx roots of K
lA = int(K**(1/2))
rB = lA + 1
if lA * rB < K:
lA += 1
# e.g. "AAABBB"
curN = lA + rB
curK = lA * rB
# minimum possible value of N is lA + rB
if curN > N:
return S
S = "A"*lA + "B"*rB
# now we can adjust the string to have pairs in the
# range [lA + 1, lA * rB]
if K < curK:
swappos = curK - K
S = swap(S, lA-1, lA-1+swappos)
# prepend Bs (which doesn't add any pairs) if required
if curN < N:
S = prependBs(S, N)
return S
createString(10, 11)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.