Posts

Prefix Sum IX

-
Image
Classic prefix sum to accomplish a linear time solution, with a linear space usage too. Execution time is ~0ms according to LC. Code is down below, cheers, ACC. Equal Score Substrings - LeetCode You are given a string  s  consisting of lowercase English letters. The  score  of a string is the sum of the positions of its characters in the alphabet, where  'a' = 1 ,  'b' = 2 , ...,  'z' = 26 . Determine whether there exists an index  i  such that the string can be split into two  non-empty   substrings   s[0..i]  and  s[(i + 1)..(n - 1)]  that have  equal  scores. Return  true  if such a split exists, otherwise return  false .   Example 1: Input:   s = "adcb" Output:   true Explanation: Split at index  i = 1 : Left substring =  s[0..1] = "ad"  with  score = 1 + 4 = 5 Right substring =  s[2..3] = "cb"  with  score = 3 + 2 = 5 Both substrings ...
Post a Comment
Read more

Don't be ashamed of N^2 IV

-
Image
If you look at the constraints for this problem, the length of the string is 1000. You can solve it in N^2 with a constant of 26, which means O(26N^2) which would mean 26,000,000 steps. That's totally feasible and you shouldn't be ashamed if it gets the job done - and fast enough. Code is down below, cheers, ACC. Longest Balanced Substring I - LeetCode You are given a string  s  consisting of lowercase English letters. A  substring  of  s  is called  balanced  if all  distinct  characters in the  substring  appear the  same  number of times. Return the  length  of the  longest balanced substring  of  s .   Example 1: Input:   s = "abbac" Output:   4 Explanation: The longest balanced substring is  "abba"  because both distinct characters  'a'  and  'b'  each appear exactly 2 times. Example 2: Input:   s = "zzabccy" Output:   4 Explanation: ...
Post a Comment
Read more

Classic Dynamic Programming X

-
Image
Very classic DP solution for this problem  Climbing Stairs II - LeetCode  with the typical hints: 1/ Min/Max problem 2/ Exponentially intractable with brute-force 3/ If you have the solutions for [0.....N-1], you can derive a formula for the solution for [N] One thing that you can do now that you have access to all LLM out there is to still continue to solve LC problems but use them to keep: A/ Improve your prompt engineering B/ Learn the capabilities of each of these models C/ Understand the solutions that they come up with, and how they might be different than yours My code is down below, along with the PROMPT used for the different models. Cheers, ACC. Code: public int ClimbStairs(int n, int[] costs) { int[] dp = new int[n + 1]; dp[0] = 0; for (int i = 1; i <= n; i++) { dp[i] = Int32.MaxValue; for (int j = 1; j <= 3; j++) { int indexFrom = i - j; int indexTo = i; if (indexFrom >= 0) ...
Post a Comment
Read more