Dynamic Programming: Basics and a Practical Example

Introduction: Dynamic programming is a problem-solving technique that can seem quite intimidating at first glance. However, once you grasp its fundamentals and see it in action, you'll find it to be a powerful tool in your coding arsenal. In this blog post, we'll demystify the basics of dynamic programming and walk through a practical example. We'll provide you with clear explanations and a complete Python program, so you can understand and apply this essential concept with confidence. Understanding Dynamic Programming: At its core, dynamic programming is all about breaking down a complex problem into smaller, overlapping subproblems. It's a technique used to efficiently solve problems by storing and reusing solutions to these subproblems, rather than recomputing them. This leads to significant improvements in runtime complexity. Example: Fibonacci Sequence with Dynamic Programming Let's start by tackling a classic problem: calculating Fibonacci numbers. The Fibonac...
Post a Comment

leetcode | Longest Substring Without Repeating Characters Solution

Source

Problem:
Given a string, find the length of the longest substring without repeating the characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        
        Set<Character> subStr = new HashSet<>();
        int maxLength = 0;
        int j = 0;
        for(int i = 0; i < s.length(); i++) {
            
            if(subStr.contains(s.charAt(i))){
                System.out.println(i +" " + subStr);
                maxLength = Math.max(maxLength, subStr.size());
                
                for(;j < i;j++) {
                    
                    subStr.remove(s.charAt(j));
                    
                    if(s.charAt(j) == s.charAt(i)) {
                        break;
                    }
                }
                j++;
            }
            subStr.add(s.charAt(i));    
        }
        maxLength = Math.max(maxLength, subStr.size());
        return maxLength;
    }
}


 Time Complexity: O(n)

Comments

Post a Comment

Popular posts from this blog

Array Transformation | biweekly-contest-12 | leetcode | Java Solution

Question Source Java Solution: class Solution {     public List<Integer> transformArray(int[] arr) {                  while(true) {             boolean isChanged = false;             int []copy = arr.clone();                          for(int i = 1; i < arr.length-1; i++) {                                 if(arr[i-1] > arr[i] && arr[i+1] > arr[i]) {                      copy[i]++;                     isChanged = true;                 }else if(arr[i-1] < arr[i] && arr[i+1] < arr[i]) {               ...
Read more

Dynamic Programming: Basics and a Practical Example

Introduction: Dynamic programming is a problem-solving technique that can seem quite intimidating at first glance. However, once you grasp its fundamentals and see it in action, you'll find it to be a powerful tool in your coding arsenal. In this blog post, we'll demystify the basics of dynamic programming and walk through a practical example. We'll provide you with clear explanations and a complete Python program, so you can understand and apply this essential concept with confidence. Understanding Dynamic Programming: At its core, dynamic programming is all about breaking down a complex problem into smaller, overlapping subproblems. It's a technique used to efficiently solve problems by storing and reusing solutions to these subproblems, rather than recomputing them. This leads to significant improvements in runtime complexity. Example: Fibonacci Sequence with Dynamic Programming Let's start by tackling a classic problem: calculating Fibonacci numbers. The Fibonac...
Read more