Understand the problem

Twenty-five crows were sitting in a tree. Three parrots flew in. What day of the week is today if the tree is oak? You may have heard of a problem, much like this one, in the past and been left speechless. It often happens that the condition provides us with vague clues that don't help solve the problem at all. Now let's talk about problems like this and how to tackle them (not about this one, the answer is obviously Tuesday).

Fundamentals

Before delving into this topic further, let's list some basic ideas you can use before even beginning to solve the problem.

• It helps to first take a step back and think about the problem fundamentally instead of starting to write the code immediately. This process is also called brainstorming. Let's say that you're going to an ice cream shop that sells three scoops and five scoops of ice cream. Would it be possible to buy a k number of scoops? At first glance, it seems that we should try to get from k to zero by subtracting 3 or 5 scoops each time. The code implementation for this approach would look something like this.

  import java.util.Scanner;
  
  public class Main {
      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          int k = sc.nextInt();
  
          while (k >= 5) {
              k -= 5;
          }
  
          while (k >= 3) {
              k -= 3;
          }
  
          if (k!=0) {
              System.out.println("NO");
          } else {
              System.out.println("YES");
          }
      }
  }
  

  In this code, we take the user input 'k', and while k is greater than or equal to 5, we subtract 5 from it. We do the same for the number 3. After the subtractions, if 'k' equals 0, we can certainly say that the answer to our problem is "YES". This, of course, would work, but it is overly complicated for the task at hand because if we think about it, only the numbers 1, 2, 4, and 7 should return the answer "NO", so we can simplify this code.

  import java.util.Scanner;
  
  public class Main {
      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          int k = sc.nextInt();
  
          switch (k) {
              case 1, 2, 4, 7 -> 
                  System.out.println("NO");
              
              default -> System.out.println("YES");
          }
      }
  }
  

  As you can see, the code becomes much simpler. All we need is a single switch case to solve the problem. As a Turkish proverb goes, "Measure a thousand times and cut once". It means that you must think before you take action. There's a lot we can learn from old sayings.

• Programming has also been around for quite a while, so it would be no surprise if you could solve a given task using an existing algorithm. For example, let's say you want to find the number of occurrences of '&' symbols in a set of strings and sort them increasingly. We can easily solve this problem by first iterating over all the strings, saving the number of desired characters in a list, and sorting that list by methods already present in the documentation, which would look something like this.

  public List<Integer> count(String[] strings){
      List<Integer> answer = new ArrayList<>();
      for (String string : strings) {
          int numberOfSymbols = 0;
          for (char c : string.toCharArray()) {
              if(c == '&') {
                  numberOfSymbols++;
              }
          }
          answer.add(numberOfSymbols);
      }
      Collections.sort(answer);
      return answer;
  }
  

As we have just seen, there's more to problem-solving than meets the eye. After all, this skill is what separates us programmers from AI. So, to avoid the AI uprising let's explore one more, and arguably the most important, shortcut to problem-solving.

Smaller problems

Sometimes it can be hard to challenge a puzzling exercise head-on, but you don't have to. Let's take the 4Sum problem from Leetcode as an example:

You are given an array nums of n integers. Return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] so that:

• 0 <= a, b, c, d < n

• a, b, c, and d are distinct.

• nums[a] + nums[b] + nums[c] + nums[d] == target

This might seem challenging at first, however, what if I told you that it could be easier? Instead of going at this problem, let's take a step back and look at the 2Sum problem. Instead of quadruplets, we need to find two numbers that add to the target.

public int[] twoSum(int[] nums, int target) {         
    for (int i = 1; i < nums.length; i++) {        
        for (int j = 1; j < nums.length; j++) {    
            if (j!=i && nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return null;
}

From this point, we can go a step further and try the 3Sum problem. It states the following:
You are given an integer array nums. Return all the triplets [nums[i], nums[j], nums[k]] so that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

public List<List<Integer>> threeSum(int[] nums) {
    int n = nums.length;
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                }
            }
        }
    }
    return res;
}

A challenge arises

Now that you have a better understanding of problem-solving, let's look at another, slightly more complex problem. The Longest Palindromic Subsequence (LPS) problem aims to find the length of the longest subsequence of a given string that is also a palindrome. A subsequence is a sequence that can be derived from another by deleting some or no elements without changing their order. Here's how to approach the LPS problem by breaking it down into smaller steps:

1. Understand the problem. Given a string, find the length of its longest palindromic subsequence.

2. Identify the base case. If the input string has only one character, the longest palindromic subsequence is the string itself, with a length of 1.

3. Define the recursive relationship:

   - If the first and last characters of the string are the same, they contribute to the LPS.
   - If the first and last characters of the string are different, the LPS will be the longest between the LPS without the first character and the LPS without the last.

4. Implement a solution using dynamic programming:

   public static int findLongestPalindromicSubsequence(String s) {
       int n = s.length();
   
       int[][] dp = new int[n][n];
   
       for (int i = 0; i < n; i++) {
           dp[i][i] = 1;
       }
   
       for (int len = 2; len <= n; len++) {
           for (int i = 0; i < n - len + 1; i++) {
               int j = i + len - 1;
               if (s.charAt(i) == s.charAt(j)) {
                   dp[i][j] = dp[i + 1][j - 1] + 2;
               } else {
                   dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
               }
           }
       }
   
       return dp[0][n - 1];
   }
   

   Now we can turn the given steps into code. We first create a double array. Then we fill the diagonal elements, meaning the elements that have equal coordinates ( dp[1,1], dp[2,2] ...), with the value of 1. After that, we follow the rules specified in step 4, and that's it.

   • Create a two-dimensional DP array with dimensions equal to the length of the input string.

   • Initialize the diagonal elements of the DP array to 1 since single characters are always palindromes.

   • Iterate through the DP array, filling in each element by comparing the characters at the corresponding indices of the input string:

     - If the characters are the same, update the DP array at (i, j) with the sum of the value at (i+1, j-1) plus 2.
     - If the characters are different, update the DP array at (i, j) with the maximum value between (i+1, j) and (i, j-1)

By breaking the LPS problem into smaller steps, you can incrementally build your understanding of the problem and develop an efficient solution.

Conclusion

In conclusion, tackling complex programming problems requires a strategic approach to ensure efficient and effective solutions. The key points to remember include:

• Understanding the fundamentals: take a step back and critically consider the problem before diving into code implementation.

• Leveraging existing algorithms: utilize existing algorithms to simplify your solutions and avoid reinventing the wheel.

• Breaking problems into smaller steps: decompose larger problems into smaller, more manageable components to uncover efficient solutions and build your understanding incrementally.

By keeping these key points in mind, you will be better equipped to navigate the intricacies of problem solving in programming and develop your skills as a software developer. However, it's also important to remember that these are only the basics. It is up to you to find ways to combine these methods, as well as create new ones, on your journey.