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.

LeetCode 1672. Richest Customer Wealth Java Solution

Problem

Richest Customer Wealth - LeetCode

Approach

• This problem involves working with a 2D array to calculate the sum of values and optimize based on it.
• Initially, I straightforwardly stored the sum of all values in an array and then found the maximum value by iterating through that array. However, with better optimization, it's possible to directly find the maximum value without needing to store values in an array.
• Algorithm:
  • In the first loop, iterate through each array.
  • In the second loop, calculate the sum of values in each array.
  • After the second loop, compare the sum of values with the current maximum and update it if the sum is higher.
  • Return the stored maximum value.

Github Link

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

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

public class Solution {
    /**
     * Calculates the maximum wealth among customers.
     *
     * @param accounts 2D array representing customers and their account wealth
     * @return Maximum wealth among customers
     */
    public int maximumWealth(int[][] accounts) {
        int max = 0; // Initialize the maximum wealth as 0.

        for (int[] listOfWealth : accounts) {
            int tempSum = 0; // Initialize temporary sum for each customer.

            for (int wealth : listOfWealth) {
                tempSum += wealth; // Add each account's wealth to the temporary sum.
            }

            max = Math.max(max, tempSum); // Update the maximum wealth if the temporary sum is greater.
        }

        return max;
    }
}

Summary of Operators in Python

Types of Arithmetic Operators in Python

Symbol	Description	Return Value
+	Addition	Varies depending on the data types
-	Subtraction	Varies depending on the data types
*	Multiplication	Varies depending on the data types
/	Division	Returns a floating-point value
//	Floor Division	Returns an integer value
%	Modulus	Returns a floating-point value
**	Exponentiation	Varies depending on the data types
and	Logical AND	Returns True or False
or	Logical OR	Returns True or False
<	Less than	Returns True or False
>	Greater than	Returns True or False
<=	Less than or equal to	Returns True or False
>=	Greater than or equal to	Returns True or False
==	Equal to	Returns True or False

+, -, *, /, //, %, **, <, >, <=, >= Table

A	B	Result
int	int	int A + B result
int	float	float A + B result
int	bool-True	int A + 1 result
int	bool-False	int A + 0 result
int	None	TypeError
int	string	TypeError
float	bool-True	float A + 1 result
float	bool-False	float A + 0 result
float	None	TypeError
float	string	TypeError
bool	None	TypeError
bool	string	TypeError
None	string	TypeError

In the early days of computer generation and the inception of programming languages, 1 represented True, and 0 represented False.

== Table

A	B	Result
int	int	Boolean result
int	float	Boolean result
int	bool	Boolean result
int	None	Boolean result
int	string	Boolean result
float	bool	Boolean result
float	None	Boolean result
float	string	Boolean result
bool	None	Boolean result
bool	string	Boolean result
None	string	Boolean result

Unlike Java, this doesn't compare classes. It compares values. Since all are objects, these comparisons are possible.

and, or Truth Tables

A	B	and	or
False	False	False	False
False	True	False	True
True	False	False	True
True	True	True	True

As shown in the table above, "and" and "or" are operations on True and False.

When different data types are used, the "or" operation returns the value of B, while the "and" operation returns the value of A.

Sum of Numbers (Arithmetic Series)

Definition

The sum of an arithmetic sequence refers to the sum of consecutive terms in a sequence where the difference between consecutive terms is constant. You can calculate the sum of an arithmetic sequence using a specific formula.

To find the sum of the sequence from 1 to n, you can use the following formula:

(First term + Last term) × Number of terms / 2

a: Starting value

b: Ending value

c: Common difference

Common difference: The constant difference between consecutive terms in an arithmetic sequence.

Mathematical Example

Let's find the sum of the sequence from 1 to 10:

a: Starting value = 1

b: Ending value = 10

c: Common difference = +1

Now, substituting these values into the formula:

Advantages

• The formula for the sum of an arithmetic sequence is simple and intuitive.
• It allows for quick calculation of the sum of large numbers of terms.
• It can be applied to general forms of arithmetic sequences.

Disadvantages

• This formula is only applicable to arithmetic sequences and cannot be used for other types of sequences.
• The number of terms must be known to use the formula.

Java Example

public class ArithmeticSeriesSum {
    public static void main(String[] args) {
				int start = 1;
        int end = 10;
        int commonDifference = 1;
        int sum = (start + end) * ((end - start) / commonDifference + 1) / 2;
        System.out.println("Sum from 1 to 10: " + sum);
    }
}

LeetCode 236. Lowest Common Ancestor of a Binary Tree Java Solution

Problem

Lowest Common Ancestor of a Binary Tree - LeetCode

Problem Solution

• This problem asks whether you know about the Lowest Common Ancestor (LCA) and if you can implement it.
• In this problem, the preprocessing step for LCA cannot be used because we cannot modify the tree nodes.
• Therefore, the usual LCA algorithm involves comparing from the two target nodes and going up to their common parent. However, in this problem, we traverse from the root down the tree, comparing each node with nodes p and q to find the LCA.

Reference

What is LCA(Lowest Common Ancestor)

Github Link

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

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

n = depth of the binary tree

public class Solution {
    /**
     * Find the lowest common ancestor of two nodes in a binary tree.
     *
     * @param root The root node of the binary tree.
     * @param p    The first node.
     * @param q    The second node.
     * @return The lowest common ancestor of nodes p and q.
     */
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // If the root is null or either p or q is the root, return the root.
        if (root == null || root == p || root == q) {
            return root;
        }

        // Recursively find the lowest common ancestor in the left and right subtrees.
        TreeNode leftLCA = lowestCommonAncestor(root.left, p, q);
        TreeNode rightLCA = lowestCommonAncestor(root.right, p, q);

        // If both leftLCA and rightLCA are not null, it means p and q are in different subtrees, and the current root is the lowest common ancestor.
        if (leftLCA != null && rightLCA != null) {
            return root;
        }
        // If leftLCA is not null, it means p and q are in the left subtree, and the lowest common ancestor is in the left subtree.
        else if (leftLCA != null) {
            return leftLCA;
        }
        // If rightLCA is not null, it means p and q are in the right subtree, and the lowest common ancestor is in the right subtree.
        else {
            return rightLCA;
        }
    }
}

Code Sequence Example

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

What is LCA(Lowest Common Ancestor)

Definition

Lowest Common Ancestor, LCA.

LCA is an algorithm or concept used in tree structures to find the closest common ancestor of two nodes.

Example

In the above binary tree, the LCA of 4 and 6 is 1.

LCA(4, 6) = 1

Purpose

The purpose of the LCA is to efficiently find the closest common ancestor of two nodes in a tree structure.

Cases to consider using LCA

You should consider using the LCA algorithm in the following cases:

• When you need to calculate the distance between two nodes in a tree structure.
• When you need to find nodes belonging to a subtree rooted at a specific node.
• When calculating the shortest path in computer networks.
• When solving collision detection and other problems in game development.

Cases not suitable for using LCA

The LCA algorithm is limited to tree structures and cannot be used in other data structures. Additionally, if the problem doesn't involve finding the common ancestor of two nodes, there is no need to use LCA.

Advantages

• It can efficiently find the LCA of two nodes with a reasonable time complexity.
• After preprocessing, query operations can be performed quickly.

Disadvantages

• The LCA algorithm is restricted to tree structures and cannot be applied to other data structures.

Implementation Steps

1. Compute the parent and depth information for each node in the binary tree.
2. This step is called preprocessing.
3. Move towards the parents of the two nodes for which you want to find the LCA.
4. While moving towards the parents, check for the first intersection of the nodes.
5. The first intersection is the LCA.

Example

import java.util.ArrayList;
import java.util.List;

class Node {
    int value;
    Node parent;
    List<Node> children;

    Node(int value) {
        this.value = value;
        this.children = new ArrayList<>();
    }
}

public class LCAExample {

    private static void preprocess(Node node, Node parent, int depth) {
        node.parent = parent;

        for (Node child : node.children) {
            preprocess(child, node, depth + 1);
        }
    }

    private static Node findLCA(Node node1, Node node2) {
        int depth1 = getDepth(node1);
        int depth2 = getDepth(node2);

        while (depth1 > depth2) {
            node1 = node1.parent;
            depth1--;
        }

        while (depth2 > depth1) {
            node2 = node2.parent;
            depth2--;
        }

        while (node1 != node2) {
            node1 = node1.parent;
            node2 = node2.parent;
        }

        return node1;
    }

    private static int getDepth(Node node) {
        int depth = 0;
        while (node.parent != null) {
            node = node.parent;
            depth++;
        }
        return depth;
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);

        root.children.add(node2);
        root.children.add(node3);
        node2.children.add(node4);
        node2.children.add(node5);
        node3.children.add(node6);
        node3.children.add(node7);

        preprocess(root, null, 0);

        Node lcaNode = findLCA(node4, node5);
        System.out.println("LCA: " + lcaNode.value); // 2

        lcaNode = findLCA(node4, node6);
        System.out.println("LCA: " + lcaNode.value); // 1

        lcaNode = findLCA(node3, node7);
        System.out.println("LCA: " + lcaNode.value); // 3
    }
}

What is Python Variables

what is Variable

symbol represent some number or String that may change.

data types

scalar and non-scalar both object

scalar

• int : integer
• float : real number
• bool : True or False
• none : Null

non-scalar

• String : data values that are made up of ordered sequences of characters, such as "hello world"

How to check data type

print(type(Variable))

addtional infomation

Case-Sensitive

a and A are different variable

Casting

x = str(4)    # "4"
y = int(4)    # 4
z = float(4) # 4.0