Given a pair of strings, Geek wants to find the better string. The better string is the string having more number of distinct subsequences.
If both the strings have equal count of distinct subsequence then return str1.
Example 1:
Input:
str1 = "gfg", str2 = "ggg"
Output: "gfg"
Explanation: "gfg" have 7 distinct subsequences whereas "ggg" have 4 distinct subsequences. 
Example 2:
Input: str1 = "a", str2 = "b"
Output: "a"
Explanation: Both the strings have only 1 distinct subsequence. 
Constraints:
1 <= str1.lenght , str2.length <= 30
Your Task:
You don't need to read input or print anything. Your task is to complete the function betterString() which takes str1 and str2 as input parameters and returns the better string.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

    def betterString(self, str1, str2):

        # Code here

Solutions:
class Solution:

	def betterString(self, str1, str2):

		def find(str1):
			count = 1
			dic = {}
			for el in str1:
				if el not in dic:
					dic[el] = count
					count *= 2
				elif el in dic:
					temp = dic[el]
					dic[el] = count
					count *= 2
					count -= temp
			return count
		cnt1 = find(str1)
		cnt2 = find(str2)
		if cnt1 >= cnt2:
			return str1
		return str2


class Solution:

	def betterString(self, str1, str2):

		def countSub(s):
			last = {}
			n = len(s)
			dp = [0] * (1 + n)
			dp[0] = 1
			for i in range(1, n + 1):
				dp[i] = 2 * dp[i - 1]
				if s[i - 1] in last:
					dp[i] = dp[i] - dp[last[s[i - 1]]]
				last[s[i - 1]] = i - 1
			return dp[n]
		a = countSub(str1)
		b = countSub(str2)
		if a < b:
			return str2
		return str1


class Solution:

	def getLen(self, st):
		dp = [1]
		lo = dict()
		for i in range(1, len(st) + 1):
			dp.append(2 * dp[i - 1])
			ch = st[i - 1]
			if ch in lo:
				j = lo[ch]
				dp[i] = dp[i] - dp[j - 1]
			lo[ch] = i
		return dp[-1]

	def betterString(self, str1, str2):
		r1 = self.getLen(str1)
		r2 = self.getLen(str2)
		if r1 >= r2:
			return str1
		else:
			return str2


class Solution:

	def betterString(self, s, t):

		def countSubSets(s):
			(c, l, d) = (1, [1], {})
			for i in range(len(s)):
				c *= 2
				if s[i] in d:
					c -= l[d[s[i]] - 1]
				d[s[i]] = i + 1
				l.append(c)
			return c
		(c1, c2) = map(countSubSets, (str1, str2))
		return str1 if c1 == c2 or c1 > c2 else str2


class Solution:

	def betterString(self, s1, s2):
		l = [0] * len(s1)
		l[0] = 2
		(h, h1) = ({}, {})
		for i in range(len(s1)):
			h[i] = h1.get(s1[i], -1)
			h1[s1[i]] = i
		for i in range(1, len(s1)):
			if h[i] == -1:
				l[i] = l[i - 1] * 2
			elif h[i] == 0:
				l[i] = l[i - 1] * 2 - 1
			else:
				l[i] = l[i - 1] * 2 - l[h[i] - 1]
		l1 = [0] * len(s2)
		l1[0] = 2
		(h3, h4) = ({}, {})
		for i in range(len(s2)):
			h3[i] = h4.get(s2[i], -1)
			h4[s2[i]] = i
		for i in range(1, len(s2)):
			if h3[i] == -1:
				l1[i] = l1[i - 1] * 2
			elif h3[i] == 0:
				l1[i] = l1[i - 1] * 2 - 1
			else:
				l1[i] = l1[i - 1] * 2 - l1[h3[i] - 1]
		if l[-1] >= l1[-1]:
			return s1
		return s2


class Solution:

	def countSubsequences(self, s):
		freq = {}
		n = len(s)
		distinctCount = [0] * (n + 1)
		distinctCount[0] = 1
		for i in range(1, n + 1):
			if s[i - 1] not in freq:
				distinctCount[i] = 2 * distinctCount[i - 1]
			else:
				distinctCount[i] = 2 * distinctCount[i - 1] - distinctCount[freq[s[i - 1]]]
			freq[s[i - 1]] = i - 1
		return distinctCount[n]

	def betterString(self, str1, str2):
		count1 = self.countSubsequences(str1)
		count2 = self.countSubsequences(str2)
		if count1 >= count2:
			return str1
		else:
			return str2


class Solution:

	def betterString(self, str1, str2):

		def count_subsequences(s):
			n = len(s)
			dp = [0] * (n + 1)
			dp[0] = 1
			last = {}
			for i in range(1, n + 1):
				dp[i] = 2 * dp[i - 1]
				if s[i - 1] in last:
					dp[i] -= dp[last[s[i - 1]] - 1]
				last[s[i - 1]] = i
			return dp[n] - 1
		count1 = count_subsequences(str1)
		count2 = count_subsequences(str2)
		if count1 == count2:
			return str1
		elif count1 > count2:
			return str1
		else:
			return str2


class Solution:

	def betterString(self, str1, str2):

		def funcall(string):
			count = 1
			dicti = dict()
			for char in string:
				if char not in dicti:
					dicti[char] = count
					count *= 2
				else:
					temp = dicti[char]
					dicti[char] = count
					count *= 2
					count -= temp
			return count
		arr1 = funcall(str1)
		arr2 = funcall(str2)
		if arr2 > arr1:
			return str2
		else:
			return str1


class Solution:

	def rec(self, s):
		n = len(s)
		dp = [1]
		m = {}
		for i in range(n):
			if s[i] in m:
				dp.append(dp[i] * 2 - dp[m[s[i]] - 1])
			else:
				dp.append(dp[i] * 2)
			m[s[i]] = i + 1
		return dp[n]

	def betterString(self, str1, str2):
		a = self.rec(str1)
		b = self.rec(str2)
		if a >= b:
			return str1
		return str2


class Solution:

	def countSub(self, str):
		last = [-1] * 127
		n = len(str)
		dp = [0] * (n + 1)
		dp[0] = 1
		for i in range(1, n + 1):
			dp[i] = 2 * dp[i - 1]
			if last[ord(str[i - 1])] != -1:
				dp[i] -= dp[last[ord(str[i - 1])]]
			last[ord(str[i - 1])] = i - 1
		return dp[n]

	def betterString(self, str1, str2):
		if self.countSub(str1) < self.countSub(str2):
			return str2
		return str1


def func(S):
	last = [-1] * 256
	dp = [0] * (len(S) + 1)
	dp[0] = 1
	for i in range(1, len(S) + 1):
		dp[i] = dp[i - 1] * 2
		if last[ord(S[i - 1])] != -1:
			dp[i] -= dp[last[ord(S[i - 1])]]
		last[ord(S[i - 1])] = i - 1
	return dp[len(S)] % int(1000000000.0 + 7)

class Solution:

	def betterString(self, str1, str2):
		a = func(str1)
		b = func(str2)
		if a >= b:
			return str1
		return str2


class Solution:

	def countSubsequence(self, strn):
		last = [-1] * 127
		N = len(strn)
		dp = [0] * (N + 1)
		dp[0] = 1
		for i in range(1, N + 1):
			dp[i] = 2 * dp[i - 1]
			if last[ord(strn[i - 1])] != -1:
				dp[i] = dp[i] - dp[last[ord(strn[i - 1])]]
			last[ord(strn[i - 1])] = i - 1
		return dp[N]

	def betterString(self, str1, str2):
		if self.countSubsequence(str1) < self.countSubsequence(str2):
			return str2
		return str1


class Solution:

	def subSequence(self, strn):
		answer = set()
		N = 1 << len(strn)
		for i in range(N):
			temp = ''
			for j in range(len(strn)):
				if i >> j & 1 == 1:
					temp += strn[j]
			answer.add(temp)
		return len(answer)

	def countSubsequence(self, strn):
		last = [-1] * 127
		N = len(strn)
		dp = [0] * (N + 1)
		dp[0] = 1
		for i in range(1, N + 1):
			dp[i] = 2 * dp[i - 1]
			if last[ord(strn[i - 1])] != -1:
				dp[i] = dp[i] - dp[last[ord(strn[i - 1])]]
			last[ord(strn[i - 1])] = i - 1
		return dp[N]

	def betterString(self, str1, str2):
		if self.countSubsequence(str1) >= self.countSubsequence(str2):
			return str1
		return str2