Given two strings: s1 and s2 with the same size, check if some permutation of string s1 can break some permutation of string s2 or vice-versa (in other words s2 can break s1).
A string x can break string y (both of size n) if x[i] >= y[i] (in alphabetical order) for all i between 0 and n-1.
 
Example 1:
Input: s1 = "abc", s2 = "xya"
Output: true
Explanation: "ayx" is a permutation of s2="xya" which can break to string "abc" which is a permutation of s1="abc".

Example 2:
Input: s1 = "abe", s2 = "acd"
Output: false 
Explanation: All permutations for s1="abe" are: "abe", "aeb", "bae", "bea", "eab" and "eba" and all permutation for s2="acd" are: "acd", "adc", "cad", "cda", "dac" and "dca". However, there is not any permutation from s1 which can break some permutation from s2 and vice-versa.

Example 3:
Input: s1 = "leetcodee", s2 = "interview"
Output: true

 
Constraints:

s1.length == n
s2.length == n
1 <= n <= 10^5
All strings consist of lowercase English letters.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Sorting

Greedy algorithms

Starter code: class Solution:
    def checkIfCanBreak(self, s1: str, s2: str) -> bool:
        

Solutions:
from collections import Counter

class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		(d1, d2) = (Counter(s1), Counter(s2))
		return self.check(d1, d2) or self.check(d2, d1)

	def check(self, d1: dict, d2: dict) -> bool:
		s = 0
		for c in 'abcdefghijklmnopqrstuvwxyz':
			s += d1[c] - d2[c]
			if s < 0:
				return False
		return True


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		c1 = collections.Counter(s1)
		c2 = collections.Counter(s2)
		(t1, t2) = (0, 0)
		(f1, f2) = (1, 1)
		for i in range(26):
			z = chr(97 + i)
			t1 += c1[z] - c2[z]
			if t1 < 0:
				f1 = 0
			t2 += c2[z] - c1[z]
			if t2 < 0:
				f2 = 0
		return f1 or f2


from collections import Counter

class Solution:

	def checkIfCanBreak(self, s1, s2):
		dic_1 = Counter(s1)
		dic_2 = Counter(s2)
		return self.check(dic_1, dic_2) or self.check(dic_2, dic_1)

	def check(self, d1, d2):
		res = 0
		for i in 'abcdefghijklmnopqrstuvwxyz':
			res += d2[i] - d1[i]
			if res < 0:
				return False
		return True


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		from collections import Counter

		def check_breakable(s1, s2):
			s1_counter = Counter(s1)
			s2_counter = Counter(s2)
			cnt = 0
			for char in 'abcdefghijklmnopqrstuvwxyz':
				cnt += s1_counter[char] - s2_counter[char]
				if cnt < 0:
					return False
			return True
		return check_breakable(s1, s2) == True or check_breakable(s2, s1) == True


class Solution:

	def checkIfCanBreak(self, s1, s2):
		s1 = sorted(s1)
		s2 = sorted(s2)
		return all((x <= y for (x, y) in zip(s1, s2))) or all((y <= x for (x, y) in zip(s1, s2)))


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		(t1, t2) = (sorted(list(s1)), sorted(list(s2)))
		for i in range(len(t1)):
			if t1[i] <= t2[i]:
				continue
			else:
				break
		else:
			return True
		for i in range(len(t1)):
			if t1[i] >= t2[i]:
				continue
			else:
				break
		else:
			return True
		return False


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1 = sorted(s1)
		s2 = sorted(s2)
		s1_bigger = False
		s2_bigger = False
		for i in range(len(s1)):
			if s1_bigger and s1[i] < s2[i]:
				return False
			if s2_bigger and s1[i] > s2[i]:
				return False
			if s1[i] < s2[i]:
				s2_bigger = True
			if s1[i] > s2[i]:
				s1_bigger = True
		return True


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		c1 = Counter(s1)
		c2 = Counter(s2)
		s = set()
		diff = 0
		for i in range(26):
			c = chr(ord('a') + i)
			diff += c1[c] - c2[c]
			if diff:
				s.add(diff > 0)
		return len(s) < 2


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1 = list(s1)
		s2 = list(s2)
		s1.sort()
		s2.sort()
		s1token = True
		for i in range(len(s1)):
			if s1[i] > s2[i]:
				s1token = False
				break
		if s1token == True:
			return True
		s2token = True
		for i in range(len(s2)):
			if s2[i] > s1[i]:
				s2token = False
				break
		if s2token == True:
			return True
		return False


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1 = sorted(s1)
		s2 = sorted(s2)
		left = True
		determined = False
		for (i, c) in enumerate(s1):
			if c > s2[i]:
				if not left and determined:
					return False
				determined = True
			elif c < s2[i]:
				if left and determined:
					return False
				left = False
				determined = True
		return True


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1 = list(s1)
		s2 = list(s2)
		s1.sort(reverse=True)
		s2.sort(reverse=True)
		match = all((x >= y for (x, y) in zip(s1, s2)))
		if match:
			return True
		s1.sort()
		s2.sort()
		match = all((y >= x for (x, y) in zip(s1, s2)))
		return match


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		arr1 = list(s1)
		arr2 = list(s2)
		arr1.sort()
		arr2.sort()
		c = 0
		for i in range(len(arr1)):
			if arr1[i] > arr2[i]:
				break
			c += 1
		if c == len(arr1):
			return True
		for i in range(len(arr1)):
			if arr1[i] < arr2[i]:
				return False
			c += 1
		return True


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		l1 = [char for char in s1]
		l1.sort()
		l2 = [char for char in s2]
		l2.sort()
		strlen = len(s1)
		flag = 0
		for i in range(strlen):
			if l1[i] >= l2[i]:
				continue
			else:
				flag = 1
				break
		if flag:
			for i in range(strlen):
				if l1[i] <= l2[i]:
					continue
				else:
					return False
		return True


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1 = sorted([c for c in s1])
		s2 = sorted([c for c in s2])
		return all((char1 <= char2 for (char1, char2) in zip(s1, s2))) or all((char1 >= char2 for (char1, char2) in zip(s1, s2)))


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		ss1 = sorted(s1)
		ss2 = sorted(s2)
		f = True
		r = True
		for (x, y) in zip(ss1, ss2):
			f = f and x >= y
			r = r and x <= y
		return f or r


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1 = sorted(s1)
		s2 = sorted(s2)
		size_t = len(s1)
		for idx in range(size_t):
			if s1[idx] == s2[idx]:
				continue
			elif s1[idx] < s2[idx]:
				ans = set(map(lambda x, y: x <= y, s1, s2))
				break
			else:
				ans = set(map(lambda x, y: x >= y, s1, s2))
				break
		if len(ans) > 1:
			return False
		return True


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1 = sorted(s1)
		s2 = sorted(s2)
		indices = [i for (i, (a, b)) in enumerate(zip(s1, s2)) if a != b]
		comparisons = [s1[i] > s2[i] for i in indices]
		return all(comparisons) or not any(comparisons)


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		arr1 = list(s1)
		arr2 = list(s2)
		arr1.sort()
		arr2.sort()
		n = len(arr1)
		flag = True
		flag1 = True
		for i in range(n):
			if arr1[i] < arr2[i]:
				flag1 = False
		flag2 = True
		for i in range(n):
			if arr1[i] > arr2[i]:
				flag2 = False
		if flag1 or flag2:
			return True
		return False


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1 = sorted(s1)
		s2 = sorted(s2)
		count1 = 0
		count2 = 0
		for i in range(len(s1)):
			if s1[i] <= s2[i]:
				count1 += 1
			if s1[i] >= s2[i]:
				count2 += 1
		if count1 == len(s1) or count2 == len(s1):
			return True
		return False


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		l1 = list(s1)
		l2 = list(s2)
		l1.sort()
		l2.sort()
		count = 0
		count1 = 0
		for i in range(len(l1)):
			if l1[i] >= l2[i]:
				count += 1
		if count == len(l1):
			return True
		for i in range(len(l2)):
			if l2[i] >= l1[i]:
				count1 += 1
		if count1 == len(l1):
			return True
		return False


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:

		def helper(d1, d2):
			s = 0
			for c in 'abcdefghijklmnopqrstuvwxyz':
				s += d1[c] - d2[c]
				if s < 0:
					return False
			return True
		c1 = collections.Counter(s1)
		c2 = collections.Counter(s2)
		return helper(c1, c2) or helper(c2, c1)


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1 = sorted(s1, reverse=True)
		s2 = sorted(s2, reverse=True)
		resultA = []
		resultB = []
		for (ch1, ch2) in zip(s1, s2):
			if ch1 >= ch2:
				resultA.append(1)
			else:
				resultA.append(0)
			if ch2 >= ch1:
				resultB.append(1)
			else:
				resultB.append(0)
		if all(resultA) == 1 or all(resultB):
			return True
		else:
			return False


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		n = len(s1)
		s1 = sorted(s1)
		s2 = sorted(s2)
		s1_tally = 0
		s2_tally = 0
		for i in range(n):
			if s1[i] >= s2[i]:
				s1_tally += 1
			if s2[i] >= s1[i]:
				s2_tally += 1
		return s1_tally == n or s2_tally == n


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		return all((ch1 <= ch2 for (ch1, ch2) in zip(sorted(s1), sorted(s2)))) or all((ch1 <= ch2 for (ch1, ch2) in zip(sorted(s2), sorted(s1))))


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		perm1 = sorted(list(s1))
		perm2 = sorted(list(s2))
		zipped = zip(perm1, perm2)
		forward = True
		backward = True
		for (x, y) in zipped:
			if ord(x) > ord(y):
				forward = False
			if ord(y) > ord(x):
				backward = False
		return forward or backward


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1_arr = [ord(x) for x in s1]
		s2_arr = [ord(x) for x in s2]
		s1_arr.sort()
		s2_arr.sort()
		s1_counter = 0
		s2_counter = 0
		for i in range(len(s1_arr)):
			if s1_arr[i] > s2_arr[i]:
				s1_counter += 1
			elif s1_arr[i] == s2_arr[i]:
				s1_counter += 1
				s2_counter += 1
			else:
				s2_counter += 1
		print((s1_counter, s2_counter))
		if s1_counter == len(s1) or s2_counter == len(s1):
			return True
		else:
			return False


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1 = sorted(list(s1))
		s2 = sorted(list(s2))
		i = 0
		while s1[i] <= s2[i]:
			if i == len(s1) - 1:
				return True
			i += 1
		i = 0
		while s2[i] <= s1[i]:
			if i == len(s1) - 1:
				return True
			i += 1
		return False


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		x = 'abcdefghijklmnopqrstuvwxyz'
		d = defaultdict(int)
		for i in range(len(x)):
			d[x[i]] = i + 1
		a1 = []
		a2 = []
		for i in range(len(s1)):
			a1.append(d[s1[i]])
			a2.append(d[s2[i]])
		a1.sort()
		a2.sort()
		(c1, c2) = (0, 0)
		for i in range(len(a1)):
			if a1[i] > a2[i]:
				c1 += 1
			elif a2[i] > a1[i]:
				c2 += 1
			else:
				c1 += 1
				c2 += 1
		if c1 == len(s1) or c2 == len(s1):
			return True
		return False


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1 = sorted([ord(s) for s in s1])
		s2 = sorted([ord(s) for s in s2])
		i = 0
		while s1[i] <= s2[i]:
			if i == len(s1) - 1:
				return True
			i += 1
		i = 0
		while s2[i] <= s1[i]:
			if i == len(s1) - 1:
				return True
			i += 1
		return False


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1sorted = ''.join(sorted(s1))
		s2sorted = ''.join(sorted(s2))
		res1 = True
		res2 = True
		for i in range(len(s1)):
			if ord(s1sorted[i]) > ord(s2sorted[i]):
				res1 = False
		for i in range(len(s1)):
			if ord(s1sorted[i]) < ord(s2sorted[i]):
				res2 = False
		return res1 or res2


class Solution:

	def check(self, d1, d2):
		for (x, y) in zip(d1, d2):
			if x <= y:
				continue
			return False
		return True

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		d1 = sorted(s1)
		d2 = sorted(s2)
		return self.check(d1, d2) | self.check(d2, d1)


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1 = sorted(s1)
		s2 = sorted(s2)
		ans1 = True
		ans2 = True
		for i in range(len(s1)):
			if s1[i] < s2[i]:
				ans1 = False
			if s2[i] < s1[i]:
				ans2 = False
		return ans1 or ans2


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		comparisons = [a >= b for (a, b) in zip(sorted(s1), sorted(s2))]
		all_true = all(comparisons)
		if not all_true:
			comparisons = [a <= b for (a, b) in zip(sorted(s1), sorted(s2))]
			all_true = all(comparisons)
		return all_true


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1list = list(s1)
		s2list = list(s2)
		s1list.sort()
		s2list.sort()
		count1 = 0
		count2 = 0
		for i in range(len(s1)):
			count1 += int(s1list[i] >= s2list[i])
		for i in range(len(s1)):
			count2 += int(s2list[i] >= s1list[i])
		return not count1 % len(s1) or not count2 % len(s1)


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		ar1 = [0 for i in range(len(s1))]
		ar2 = [0 for i in range(len(s2))]
		for i in range(len(s1)):
			ar1[i] = ord(s1[i])
			ar2[i] = ord(s2[i])
		ar1.sort()
		ar2.sort()
		flag1 = False
		flag2 = False
		for i in range(len(ar1)):
			if ar1[i] - ar2[i] < 0:
				flag1 = True
			elif ar2[i] - ar1[i] < 0:
				flag2 = True
		return flag1 == False or flag2 == False


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		ans1 = [a <= b for (a, b) in zip(sorted(s1), sorted(s2))]
		ans2 = [a >= b for (a, b) in zip(sorted(s1), sorted(s2))]
		if len(set(ans1)) == 1 or len(set(ans2)) == 1:
			return True
		return False


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1 = sorted(s1)
		s2 = sorted(s2)

		def check(s1, s2):
			c = 0
			n = len(s1)
			for i in range(n):
				if s1[i] >= s2[i]:
					c = c + 1
			return c == n
		return check(s2, s1) or check(s1, s2)


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		return all([a <= b for (a, b) in zip(sorted(s1), sorted(s2))]) or all([b <= a for (a, b) in zip(sorted(s1), sorted(s2))])


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1 = sorted(s1)
		s2 = sorted(s2)
		ge = 0
		le = 0
		for i in range(len(s1)):
			if s1[i] >= s2[i]:
				ge += 1
			if s1[i] <= s2[i]:
				le += 1
		return ge == len(s1) or le == len(s1)


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1 = sorted(s1)
		s2 = sorted(s2)
		a1 = [s1[i] >= s2[i] for i in range(len(s1))]
		a2 = [s1[i] <= s2[i] for i in range(len(s1))]
		return False not in a1 or False not in a2


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:

		def ifbreaks(a, b):
			a = sorted(a)
			b = sorted(b)
			for i in range(len(a)):
				if a[i] < b[i]:
					return False
			return True
		return ifbreaks(s1, s2) or ifbreaks(s2, s1)


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		l1 = sorted(list(s1))
		l2 = sorted(list(s2))
		case1 = True
		case2 = True
		for i in range(len(l1)):
			if l1[i] > l2[i]:
				case1 = False
		for i in range(len(l1)):
			if l2[i] > l1[i]:
				case2 = False
		return case1 or case2


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		l1 = list()
		l2 = list()
		n = len(s1)
		for i in range(0, n):
			l1.append(s1[i:i + 1])
		l1.sort()
		for i in range(0, n):
			l2.append(s2[i:i + 1])
		l2.sort()
		indicator = False
		l1_test = list()
		for i in range(0, n):
			if l1[i] >= l2[i]:
				l1_test.append(1)
		if len(l1_test) == len(l1):
			indicator = True
		l2_test = list()
		for i in range(0, n):
			if l2[i] >= l1[i]:
				l2_test.append(1)
		if len(l2_test) == len(l2):
			indicator = True
		return indicator


class Solution:

	def checkIfCanBreak(self, s1: str, s2: str) -> bool:
		s1 = ''.join(sorted(s1))
		s2 = ''.join(sorted(s2))
		cnt1 = 0
		cnt2 = 0
		for i in range(len(s1)):
			if s1[i] >= s2[i]:
				cnt1 += 1
			if s2[i] >= s1[i]:
				cnt2 += 1
		print((cnt1, cnt2))
		return cnt1 == len(s1) or cnt2 == len(s2)