Interview05_String_Manipulation

## Interview Preparation Kit
## String Manipulation




## Strings: Making Anagrams
#!/bin/python3
import math
import os
import random
import re
import sys

#Complete the makeAnagram function below.
# Option 1
from collections import Counter
def makeAnagram(a, b):
    a = Counter(a)
    b = Counter(b)
    intersection = a & b
    a_removal = a - intersection
    b_removal = b - intersection
    result = sum(a_removal.values()) + sum(b_removal.values())
    return result

# Option 2
from collections import Counter
def makeAnagram(a, b):
    #Counter for each string
    dict_a, dict_b = Counter(a), Counter(b) 
    #Counter for letters in 'a' and not in 'b' and viceversa
    letters_removed = (dict_a-dict_b) + (dict_b-dict_a)
    #Sum the occurrence of each extra letter
    return sum(letters_removed.values())

# Option 3
def makeAnagram(a, b):
    counter = 0
    for i in range(len(a)):
        t = a[i+1:].count(a[i])
        if a[i] not in b:
            counter += 1
        else: 
            if t >= b.count(a[i]):
                counter += 1
    for i in range(len(b)):
        t = b[i+1:].count(b[i])
        if b[i] not in a:
            counter += 1
        else:
            if t >= a.count(b[i]):
                counter += 1
    return counter

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    a = input()
    b = input()
    res = makeAnagram(a, b)
    fptr.write(str(res) + '\n')
    fptr.close()




## Alternating Characters
#!/bin/python3
import math
import os
import random
import re
import sys

# Complete the alternatingCharacters function below.
# Option 1
def alternatingCharacters(s):
    c = 0   # count
    for i in range(len(s)-1):
        if s[i]==s[i+1]:
            c += 1
    return c

# Option 2
def alternatingCharacters(s):
    return len([i for i in range(len(s)-1) if s[i]==s[i+1]])
    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    q = int(input())
    for q_itr in range(q):
        s = input()
        result = alternatingCharacters(s)
        fptr.write(str(result) + '\n')
    fptr.close()




## Sherlock and the Valid String
#!/bin/python3
import math
import os
import random
import re
import sys

# Complete the isValid function below.
# Option 1
from collections import Counter
def isValid(s):
    freq_list = list(Counter(s).values())
    first = freq_list[0]
    flag = 0
    for i in range(1, len(freq_list)):   
        if abs(freq_list[i] - first) >= 1 :
            flag += 1
    if flag > 1 :
        return 'NO'
    else:
        return 'YES'

# Option 2
from collections import Counter
def isValid(s):
    char_dict = Counter(s)
    c = 0
    for char in s:
        if char not in char_dict:
            char_dict[char] = 1
        else:
            char_dict[char] += 1
    current_value = 0
    previous_value = 0
    for index, key in enumerate(char_dict):
        current_value = char_dict[key]
        if index == 0:
            previous_value = char_dict[key]
        if abs(current_value - previous_value) >= 1:
            c += 1
        if c > 1:
            return 'NO'
    return 'YES'

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    s = input()
    result = isValid(s)
    fptr.write(result + '\n')
    fptr.close()




## Special String Again
#!/bin/python3
import math
import os
import random
import re
import sys

# Complete the substrCount function below.
# Option 1
def substrCount(n, s):
    l = []
    c = 0   #count
    ref = None
    for i in range(n):
        if s[i] == ref:
            c += 1
        else:
            if ref is not None:
                l.append((ref, c))
            ref = s[i]
            c = 1
    l.append((ref, c))

    ans = 0
    for i in l:
        ans += (i[1] * (i[1] + 1)) // 2
    for i in range(1, len(l) - 1):
        if l[i - 1][0] == l[i + 1][0] and l[i][1] == 1:
            ans += min(l[i - 1][1], l[i + 1][1])

    return ans


# Option 2
def substrCount(n, s):
    count = 0
    current_char = ''
    current_count = 0
    previous_char = ''
    previous_count = 0
    before_middle = 0
    count_after_middle = False
    for c in s:
        if c == current_char:
            current_count += 1
        else:
            if count_after_middle:
                count_after_middle = False
                count += min(current_count, before_middle)
            if current_count == 1 and c == previous_char:
                count_after_middle = True
                before_middle = previous_count
            count += combs(current_count)
            previous_char = current_char
            previous_count = current_count
            current_char = c
            current_count = 1
    if count_after_middle:
        count += min(current_count, before_middle)
    count += combs(current_count)
    return int(count)

def combs(n):
    return int((n + 1) * n)/2


# Option 3
def substrCount(n, s):
    total=0
    l1 = list(s)
    l2 = list()
    pre = l1[0]
    cnt1 = 1
    for i in range(1,n):
        if l1[i] == pre:
            cnt1+=1
        else:
            l2.append({pre:cnt1})
            pre = l1[i]
            cnt1 = 1
    l2.append({pre:cnt1})
    # case #1
    for item in l2:
        for k,v in item.items():
            total+=v*(v+1)//2
    # case #2
    l_k=""
    l_v=0
    m_k=""
    m_v=0
    for item in l2:
        for k,v in item.items():
            if m_v==1:
                if l_k == k:
                    total+=min(l_v,v)
            l_k=m_k
            l_v=m_v
            m_k=k
            m_v=v
    return total

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    n = int(input())
    s = input()
    result = substrCount(n, s)
    fptr.write(str(result) + '\n')
    fptr.close()




## Common Child
"""
Common computer science problem: 
https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
"""
#!/bin/python3
import math
import os
import random
import re
import sys

# Complete the commonChild function below.
def commonChild(s1, s2):
    # row 0 = 0, column 0  = 0
    l1 = len(s1)
    l2 = len(s2)
    # we only need history of previous row
    lcs = [[0]*(len(s1)+1) for _ in range(2)]
    #lcs_letters = [['']*(len(s1)+1) for _ in range(2)]
    
    # i in s1 = i+1 in lcs
    for i in range(l1):
        # get index pointers for current and previous row
        li1 = (i+1)%2
        li = i%2
        # j in s1 = j+1 in lcs
        for j in range(l2):
            # i and j are used to step forward in each string.
            # Now check if s1[i] and s2[j] are equal 
            if s1[i] == s2[j]:
                # Now we have found one longer sequence 
                # than what we had previously found.
                # so add 1 to the length of previous longest
                # sequence which we could have found at
                # earliest previous position of each string,
                # therefore subtract -1 from both i and j
                lcs[li1][j+1] = (lcs[li][j] + 1) 
                #lcs_letters[li1][j+1] = lcs_letters[li][j]+s1[li]

            # if not matching pair, then get the biggest previous value
            elif lcs[li1][j] > lcs[li][j+1]:
                lcs[li1][j+1] = lcs[li1][j] 
                #lcs_letters[li1][j+1] = lcs_letters[li1][j]
            else:
                lcs[li1][j+1] = lcs[li][j+1] 
                #lcs_letters[li1][j+1] = lcs_letters[li][j+1]
    #print(lcs_letters[(i+1)%2][j+1])
    return lcs[(i+1)%2][j+1]

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    s1 = input()
    s2 = input()
    result = commonChild(s1, s2)
    fptr.write(str(result) + '\n')
    fptr.close()




## end ##