here is an simple python code for the same: count=0 for i in range(1,len(s),2)): if s[i]!=s[i-1]: count+=1 return count ofc clear the indentation coz its tough to align them out here
Guys, I could use some advice. I solved this problem with top-down DP (so recursion + memoization) and I get TLE (time limit exceeded). I thought top-down and bottom-up approaches have similar time complexity? Is it anybody else having these issues? I swear my top-down DP solutions usually get TLE when I submit on Leetcode.
@@techdose4u I know you're very busy, but I would really appreciate the insight :) class Solution: def minChanges(self, s: str) -> int: n = len(s)
# Memoization table memo = {}
# Helper function to calculate the minimum changes to make a substring all '0's or all '1's def min_changes(start, end): count_zero = 0 count_one = 0 for i in range(start, end): if s[i] == '0': count_one += 1 else: count_zero += 1 return min(count_zero, count_one) # Top-down DP function with memoization def dp(start): # If we reach the end of the string, no more changes are needed if start == n: return 0
# If we have already computed the result for this starting point, return it if start in memo: return memo[start]
result = float('inf')
# Try partitioning the string at every even-length partition for end in range(start + 2, n + 1, 2): # Ensure even length partitions # Calculate the changes for making the substring s[start:end] beautiful changes = min_changes(start, end) # Recurse on the rest of the string after the partition result = min(result, changes + dp(end))
# Store the result in the memo table memo[start] = result return result # Start the DP from the beginning of the string return dp(0)
its seems easy but kind of tricky
was able to pass 119 test cases by my own
Thank you for the explaination :)
yepp :)
here is an simple python code for the same:
count=0
for i in range(1,len(s),2)):
if s[i]!=s[i-1]:
count+=1
return count
ofc clear the indentation coz its tough to align them out here
thanks :)
welcome :)
sir super explanation
Appreciate it!
Guys, I could use some advice. I solved this problem with top-down DP (so recursion + memoization) and I get TLE (time limit exceeded). I thought top-down and bottom-up approaches have similar time complexity? Is it anybody else having these issues? I swear my top-down DP solutions usually get TLE when I submit on Leetcode.
Your code would make it easy to understand:)
@@techdose4u I know you're very busy, but I would really appreciate the insight :)
class Solution:
def minChanges(self, s: str) -> int:
n = len(s)
# Memoization table
memo = {}
# Helper function to calculate the minimum changes to make a substring all '0's or all '1's
def min_changes(start, end):
count_zero = 0
count_one = 0
for i in range(start, end):
if s[i] == '0':
count_one += 1
else:
count_zero += 1
return min(count_zero, count_one)
# Top-down DP function with memoization
def dp(start):
# If we reach the end of the string, no more changes are needed
if start == n:
return 0
# If we have already computed the result for this starting point, return it
if start in memo:
return memo[start]
result = float('inf')
# Try partitioning the string at every even-length partition
for end in range(start + 2, n + 1, 2): # Ensure even length partitions
# Calculate the changes for making the substring s[start:end] beautiful
changes = min_changes(start, end)
# Recurse on the rest of the string after the partition
result = min(result, changes + dp(end))
# Store the result in the memo table
memo[start] = result
return result
# Start the DP from the beginning of the string
return dp(0)
sir java code
It will be there in the description :)
how one can develop approach or logic and implement towards the problem solving in dsa
spend more time per problem.
keep solving more problems consistently