Given the username our task is to identify the gender of the user. if the number of distinct characters in one's user name is odd, then he is a male, otherwise she is a female. To solve this problem we only need to know the number of distinct characters in the username. Then determine whether it is odd or even.

1. To solve this problem without the help of any data structure is by counting number of duplicated characters within the whole string and then take the difference between the length of the whole user name and the number of duplicated characters. Their difference will give us the number of distinct characters.
2. What is the popular data Structure we use to remove duplicates? As you guessed $SET$S.

user_name = input()
n = len(user_name)
count = 0
for i in range(n):
 for j in range(i+1, n):
 if user_name[i] == user_name[j]:
 count += 1
 break
res = n - count
if res % 2 == 0:
 print("CHAT WITH HER!")
else:
 print("IGNORE HIM!")

Time complexity: O(n^2) Space complexity: O(1)

User_name = set(input())
if len(User_name) % 2 == 0:
 print("CHAT WITH HER!")
else:
 print("IGNORE HIM!")

Time complexity: O(n) Space complexity: O(1)

For this problem, we can rephrase the question as, for given number of swaps swap any adjacent ("B" then "G")'s to ("G" then "B").

intuition : iterate through the entire array and swap the Boys and Girls that are next to each other. One edge case to consider is to pass the $$$i+1$$$ iteration if $$$i$$$ matches the given pattern because it's already processed because of the swap.

import sys
input = sys.stdin.readline

def invr():
    return(map(int,input().split()))
length, swaps = invr()
string = input()
# prepare character array
char = [ch for ch in string]
 
for _ in range(swaps):
    i = 0
    while i < length-1:
       # check adjacent boys and girls and swap them
        if char[i] == 'B' and char[i+1] =='G':
            char[i], char[i+1] = char[i+1], char[i]
            # pass the next i since its already swapped
            i += 1
        i += 1
        
print(''.join(char))

Time complexity : O(n*m) where n is string length and m is number of swaps Space complexity : O(n) we are using external character array

To solve this question we are going to use the hashmap data structure. We store the name of client as a key and the number of registration for the same name as a value.

If the input name's value in the hashmap equals one the registration went successfully, if greater than one it registers the name + value of that name.

public class RegistrationSystem {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
        // solution starts................................................................
        Map<String, Integer> map = new HashMap<>();
        int n =  Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++){
            String data = br.readLine();
            int freq = map.getOrDefault(data, 0) +1;
            map.put(data, freq);
            if(map.get(data) == 1){
              System.out.println("OK");
            }else{
                System.out.println(data  + (map.get(data) - 1));
            }
        }
       // solution ends....................................................................
       output.flush();
    }
}

Let $$$A$$$ be a list of the interestingness of the topic of length $$$n$$$, where $$$ai$$$ is the interestingness of the $$$i-th$$$ topic for the teacher. Let $$$B$$$ be a list of the interestingness of the topic of length $$$n$$$, where $$$bi$$$ is the interestingness of the $$$i-th$$$ topic for the student.

Good pair of topics = pair($$$i, j$$$), where $$$i < j$$$ and $$$ai + aj > bi + bj$$$

$$$Approach 1$$$: Bruteforce (Time Limit Exceeded)

The brute force solution would be iterating over an array A and finding topic $$$bj$$$, where $$$j < i$$$ and $$$ai - bi > bj - aj$$$ for each $$$ai$$$. This requires two-layer looping and time complexity is $$$O(n^2)$$$, which is unacceptable for this problem.

$$$Approach 2$$$: Binary Search

Let’s rewrite the equation:

$$$ai - bi > bj - aj$$$ ==> $$$ai - bi > - (aj - bj)$$$ ==> $$$(ai-bi) + (aj - bj) > 0$$$

$$$ai - bi$$$ is the difference between the interestingness of the $$$i-th$$$ topic for the teacher and the student. We can now build an array $$$c$$$, where $$$ci = ai - bi$$$ The problem is now simplified to finding pairs of indices $$$i$$$ and $$$j$$$, where $$$ci + cj > 0$$$ Now, the solution would be, to sort the array $$$c$$$ and find the leftmost index $$$j$$$ at which $$$ci + cj > 0$$$ for each $$$ci$$$, where $$$ci <= 0$$$. Leftmost index $$$j$$$, can be found with binary search. Add $$$n - j$$$ to the answer, because topics after indices $$$j$$$ including $$$j$$$ are all good pairs, with topic $$$ci$$$. For $$$ci$$$, where $$$ci > 0$$$, add $$$(n - i + 1)$$$ to the answer, this makes sure the same pairs of topics won’t be added to the answer multiple times.

def binary_search(diff, low, high):
 
    i = low - 1
    best = False
 
    while low <= high:
        mid = low + (high - low)//2
 
        if diff[mid] + diff[i] > 0:
            best = mid
            high = mid-1
        else:
            low = mid + 1
    
    return best
    
def solve(a, b):
    count = 0
    diff  = []
 
    for i in range(t):
        diff.append(a[i] - b[i])
    
    diff.sort()
    n = len(diff)
 
    for i in range(n):
        if diff[i] > 0: count += (n - (i + 1))
        else:
            idx = binary_search(diff, i + 1, n -1)
            if idx:
                count += (n - idx)
 
    return count
 
if __name__ == '__main__':
 
    t = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
 
    print(solve(a, b))

Time Complexity: $$$O(nlogn)$$$, $$$n$$$ for iterating through the array and $$$logn$$$ for finding the leftmost index $$$j$$$ where $$$ci + cj > 0$$$ \n Space Complexity: $$$O(1)$$$, if one of the two arrays is reused to build an array $$$c$$$