GFG Count the Substrings Java Solution

Problem

Problem_Link

Solution Approach

• Condition: Substrings with an equal number of uppercase and lowercase letters
• If the difference between the uppercase and lowercase letters at the starting and ending positions of a specific substring is the same, then that substring satisfies the condition.

Example: “AbaBBa”

• The total number of substrings for the given example is 21, and the number of substrings that meet the condition is 7.
• To calculate the uppercase-lowercase difference, we use +1 for uppercase and -1 for lowercase letters.
• The starting point has no uppercase-lowercase difference, so it is 0.

Index	None	0	1	2	3	4	5
Element	Start	A	b	a	B	B	a
Uppercase-Lowercase Difference	0	1	0	-1	0	1	0

Substrings with the same uppercase-lowercase difference are considered satisfying the condition.

Substring	Index	Uppercase-Lowercase Difference
Ab	None~2	0
aB	2~4	0
Ba	4~6	0
AbaB	None~4	0
baBB	1~5	0
aBBa	2~6	0
AbaBBa	1~5	1

• The first index is not included, and the last index is included. This is because the starting point is 0, and there is no index for it.

Time Complexity: O(n), Space Complexity: O(n)

import java.util.HashMap;
import java.util.Map;

public class BalancedSubstring {
    public static void main(String[] args) {
        String S = "AbaBBa";
        System.out.println(countSubstring(S));
    }

    public static int countSubstring(String S) {
        int n = S.length();
        int count = 0;
        int diff = 0;
        Map<Integer, Integer> diffMap = new HashMap<>();

        // Initialize diffMap with difference 0
        diffMap.put(0, 1);

        for (int i = 0; i < n; i++) {
            char c = S.charAt(i);

            // Update the uppercase-lowercase difference
            if (Character.isUpperCase(c)) {
                diff++;
            } else if (Character.isLowerCase(c)) {
                diff--;
            }

            // Increase count based on previously encountered difference
            // If the current difference was encountered before, it means there exists a substring with equal counts of uppercase and lowercase letters
            count += diffMap.getOrDefault(diff, 0);

            // Update the current difference and its count in the diffMap
            diffMap.put(diff, diffMap.getOrDefault(diff, 0) + 1);
        }

        return count;
    }
}

Explanation

1. First, initialize a diffMap HashMap. This map is used to store the difference between the counts of uppercase and lowercase letters. Since the initial difference is 0, we add (0, 1) to the map.
2. Use a for loop to iterate through the input string S. The loop runs from index 0 to one less than the length of the string.
3. Retrieve the character c at the current index and determine if it is uppercase or lowercase. If it's uppercase, increment the diff variable by 1; if it's lowercase, decrement diff by 1.
4. If the current difference diff has been encountered before, it means there exists a substring with an equal number of uppercase and lowercase letters. Therefore, add the count of such substrings to the count variable. If the difference hasn't been encountered before, use the getOrDefault method to retrieve 0.
5. Update the diffMap using the current difference diff. If diff already exists in the map, increment its count by 1; if not, add the new difference to the map with a count of 1.
6. After the for loop finishes, return the value stored in count. This value represents the number of substrings that meet the condition of having an equal number of uppercase and lowercase letters.

Powerfull Integer Problem Solved: Uncover the Most Efficient Java Algorithm

 

Problem

Problem_Link

Problem Solving Approach

1. Traverse through all the numbers in the intervals and store their frequencies in a HashMap.
2. Sort the hashmap based on the keys.→in worst case, O(n log n)
3. Find the maximum powerful integer by iterating through the sorted hashmap, which occurs at least k times.

Time Complexity: O(n log n), Space Complexity: O(n)

https://github.com/eunhanlee/powerfullInteger/blob/master/read%20me.md

import java.util.*;
class Solution {

    /**
     * This method takes in the number of intervals n, the 2D integer array of intervals interval, and the minimum number of occurrences k for a number to be considered powerful.
     * It returns the powerful integer which occurs at least k times. If multiple integers have at least k occurrences, the maximum integer out of all those elements is returned.
     * If no integer occurs at least k times, -1 is returned.
     *
     * @param n         the number of intervals
     * @param interval  the 2D integer array of intervals where interval[i] = [start, end]
     * @param k         the minimum number of occurrences for a number to be considered powerful
     * @return the powerful integer which occurs at least k times, or -1 if no integer occurs at least k times
     */
    public static int powerfullInteger(int n, int[][] interval, int k) {
        // A hashmap to store the frequency of each number
        Map<Integer, Integer> map = new HashMap<>();
        // The maximum powerful integer that occurs at least k times, if there is no, return -1
        int maxPowerful = -1;

        // Loop through each interval and update the frequency of each number in the hashmap
        for (int i = 0; i < n; i++) {
            for (int j = interval[i][0]; j <= interval[i][1]; j++) {
                map.put(j, map.getOrDefault(j, 0) + 1);
            }
        }

        // Sort the hashmap by key
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort(Map.Entry.comparingByKey());

        // find the maximum powerful integer
        for (Map.Entry<Integer, Integer> val : list) {
            if (val.getValue() >= k) {
                maxPowerful = val.getKey();
            }
        }

        return maxPowerful;
    }
}

find number Problem Solved: Uncover the Most Efficient Java Algorithm

Problem

Problem_Link

Problem Solving Approach

• Odd digit numbers have a pattern

  1	3	5	7	9
  11	13	15	17	19
  31	33	35	37	39
  51	53	55	57	59
  71	73	75	77	79
  91	93	95	97	99
  101	103	105	107	109

• As seen above, the pattern repeats every 5 numbers.

• Therefore, we can know the position of each digit by dividing N by 5.

• If we know the position of each digit, we can find out what number will be in that position (1, 3, 5, 7, 9)

• Let's take the 13th odd digit number as an example

  • The rightmost digit (ones place) in 13 is the 3rd.

  • According to the odd digit pattern, the third number is 5.

  • The second rightmost digit (tens place) in 13 is the 2nd.

  • According to the odd digit pattern, the second number is 3.

  • In conclusion, the 13th odd digit number is 35.

• Let's take the 27th odd digit number as an example

  • The rightmost digit (ones place) in 27 is the (27%5) 2nd.

  • According to the odd digit pattern, the second number is 3.

  • Excluding the calculated digits from 27, we get 27-27%5 = 27/5=5.

  • The second rightmost digit (tens place) is the (5%5) 5th.

  • According to the odd digit pattern, the fifth number is 9.

  • In conclusion, the 27th odd digit number is 93.

• There is something slightly incorrect with the above pattern. For example, 5%5 is 0. However, we want the pattern to follow the table above.

  - n % 5 = 0 //5th number = 9
  - n % 5 = 1 //1th number = 1
  - n % 5 = 2 //2th number = 3
  - n % 5 = 3 //3th number = 5
  - n % 5 = 4 //4th number = 7

  To fix this, we subtract 1 from n.

  - n-1 % 5 = 0 //1th number = 1
  - n-1 % 5 = 1 //2th number = 3
  - n-1 % 5 = 2 //3th number = 5
  - n-1 % 5 = 3 //4th number = 7
  - n-1 % 5 = 4 //5th number = 9

• Lastly, when we get 0, 1, 2, 3, 4, the actual numbers we want are 1, 3, 5, 7, 9. To optimize this, we multiply by 2 and add 1.

  0*2+1=1
  2*2+1=3
  3*2+1=5
  4*2+1=7
  5*2+1=9

Time O(log n), Space O(1)

https://github.com/eunhanlee/findNumber_Solution_gfg.git

class Solution
{
    /**
     * Finds the Nth number containing only odd digits.
     *
     * @param N The position of the desired number.
     * @return The Nth number containing only odd digits.
     */
    public long findNumber(long N)
    {
        // The variable to store the final result
        long result = 0;
        // The variable to represent the digit position (1, 10, 100, ...)
        long position = 1;

        // Continue until N is greater than 0
        while (N > 0)
        {
            // Calculate the odd digit by subtracting 1 from N and dividing by 5
            long oddDigit = ((N - 1) % 5) * 2 + 1;
            // Subtract 1 from N and divide by 5 to prepare for the next digit calculation
            N = (N - 1) / 5;
            // Add the odd digit multiplied by the current position to the result
            result += oddDigit * position;
            // Move to the next digit position
            position *= 10;
        }

        // Return the Nth number containing only odd digits
        return result;
    }
}

Explanation

• The given integer N is repeatedly divided by 5 during the computation process, which reduces its value. In this process, odd-digit numbers are generated. The loop continues as long as N is greater than 0.

• With each iteration, N is updated to (N - 1) / 5. This process reduces N by more than half, causing N to decrease significantly with each iteration. Since N is almost halved with each iteration, the time complexity can be considered as O(log N).