https://www.acmicpc.net/problem/2607
initial
I tried thinking of Counter, which is a dictionary, to count number of each character as value and the character itself as key. But if we are just comparing counter1==counter2 then it is relatively straightforward but we have to check if the 2 strings differ by just 1 character. But the strings can differ by 1 more of the same character or 1 more of another character. For example, DOG and GOL (differs by 1 diff char) ok, DOG and DOOG(differ by 1 same char) ok.
So counter doesnt work for these kind of checks. So what if iter through each string and compare with the original string, that is converted to list via list(), and use .remove() to remove the same character from the original string. We HAVE to convert it to list cuz .remove() is for a list, not string. If a specific char is not in the original string - either cuz it is popped or it is a different char, then we increment count. After iterating through the string, if count >2, it means there are 2 or more diff char so invalid. Else, we increment ans. But what if our original string is longer than the iter string like GOOOOOD vs GOD? Then no matter if we pop the iter string from the original string, we still have OOOO left so this needs to be marked as invalid too. So an additional check is if count <2 AND len(original)<2, we increment ans.
revisited may 23rd
i was thinking of using a dictionary and incrementing invalid count when
1) no such key (alphabet) is found in the dict
2) for that key alphabet, the value is already 0 (i.e. there are extra characters in the given string like if original string is DOG and given string is DOOG)
for removing alphabet, we cant check with keys so as we iter through the dictionary keys, if there are more or equal to 2 alphabets as values remaining, it is invalid. (DOOOO VS D) then 0:4 would be remaining.
but converting string to list and comparing 2 strings and removing each character via remove is clever and more convienent
solution
n = int(input())
lst = []
for _ in range(n):
lst.append(input())
tmp = lst[0]
ans = 0
for i in range(1, n):
word = lst[i]
count = 0
ori = list(tmp) # Use list() to create a copy
for w in word:
if w in ori:
ori.remove(w)
else:
count += 1
if count < 2 and len(ori) < 2:
ans += 1
print(ans)complexity
Reading Input (O(n m)): Reading the n words, each with a maximum length of m, takes O(n m) time.
Loop Over Words (O(n m)): The outer loop runs for each word.
Nested Loop Over Characters (O(m^2)): The inner loop runs for each character in the words, and in the worst case, it performs a linear search and removal in the list, which takes O(m) for each character.
The overall time complexity is O(n m^2).
Space Complexity:
List lst (O(n m)): The list stores n words, each with a maximum length of m.
String tmp (O(m)): The tmp string stores the first word, which has a maximum length of m.
List ori (O(m)): The ori list stores a copy of the tmp string.
The overall space complexity is O(n m).
