week2 DSA 05/04, prefix, frequency Array

-





































problem statement: https://leetcode.com/problems/find-the-highest-altitude/description/

//highest altituade
class Solutation {
public:
int largestAltitued (vecotr <int> & gain ) { 
int n = gani.size();
vector<int>alt(int,0);
for(int i = 1; i<= n; i++;) {
alt[i] = alt [i-1] + gain[i-1];
}
int max_el = *max_elemenet(alt.begin(), alt.end());
reutrn max_el;
}
};




                                          **normal way of for loops to count frequency**
#include <iostream>
#include <string>
using namespace std;

int main() {
    string str = "hello";
    int freq[26] = {0}; // Array to store frequency of each letter

    // Calculate frequency of each character
    for (char c : str) {
        freq[c - 'a']++; // Increment the count for this character
    }

    // Display the frequency of each character
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            cout << char(i + 'a') << ": " << freq[i] << endl;
        }
    }
    return 0;
}


//traditional for loop using count frequency
**Code**
#include <iostream>
#include <string>
using namespace std;

int main() {
    string str = "hello"; // The input string
    int freq[26] = {0}; // Array to store frequency of each letter, initialized to zero

    // Calculate frequency of each character using a traditional for loop
    for (int i = 0; i < str.length(); i++) {
        char c = str[i]; // Access the character at index i
        if (c >= 'a' && c <= 'z') {
            freq[c - 'a']++; // Increment the count for this character
        }
    }

    // Display the frequency of each character
    cout << "Character Frequencies:\n";
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) { // Only display characters that appear in the string
            cout << char(i + 'a') << ": " << freq[i] << endl;
        }
    }

    return 0;
}

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Certainly! Let's go through this C++ code step-by-step, explaining each part in detail, including how the character frequencies are stored in the `freq` array.

### 1. **Main Function Declaration**

```cpp
int main() {
```
The `main` function is the entry point of the program, where execution starts.

### 2. **Input String Declaration and Initialization**

```cpp
string str = "hewerllo"; // The input string
```
- `string str`: Declares a string variable named `str`.
- `"hewerllo"`: Initializes `str` with the value "hewerllo", which contains the characters whose frequencies we want to count.

### 3. **Frequency Array Declaration and Initialization**

```cpp
int freq[26] = {0}; // Array to store frequency of each letter, initialized to zero
```
- `int freq[26]`: Declares an integer array `freq` of size 26. This size corresponds to the 26 letters in the English alphabet.
- `{0}`: Initializes all elements of the `freq` array to 0. This array will store the frequency of each lowercase letter, where `freq[0]` corresponds to 'a', `freq[1]` to 'b', and so on up to `freq[25]` for 'z'.
  • Each index corresponds to a letter of the alphabet, starting from 0 for 'a' to 25 for 'z'.
  • The value at each index represents the frequency of the respective letter in the input string "hewerllo".


### 4. **Calculating the Frequency of Each Character**

```cpp
for (int i = 0; i < str.length(); i++) {
    char c = str[i]; // Access the character at index i
    if (c >= 'a' && c <= 'z') {
        freq[c - 'a']++; // Increment the count for this character
    }
}
```

#### a. **Loop Initialization and Iteration**
```cpp
for (int i = 0; i < str.length(); i++) {
```
- `int i = 0`: Initializes the loop counter `i` to 0.
- `i < str.length()`: The loop continues as long as `i` is less than the length of the string `str`. `str.length()` returns the number of characters in the string, which is 8 for "hewerllo".
- `i++`: Increments the loop counter `i` by 1 after each iteration.

This loop iterates over each character in the string.

#### b. **Accessing Each Character**
```cpp
char c = str[i]; // Access the character at index i
```
- `char c = str[i];`: Retrieves the character at index `i` in the string `str` and stores it in the variable `c`.
- For example:
  - When `i = 0`, `c = 'h'`
  - When `i = 1`, `c = 'e'`
  - And so on.

#### c. **Checking if the Character is a Lowercase Letter**
```cpp
if (c >= 'a' && c <= 'z') {
```
- `c >= 'a' && c <= 'z'`: This condition checks if the character `c` is between 'a' and 'z' inclusive, ensuring that it is a lowercase letter.

#### d. **Updating the Frequency Array**
```cpp
freq[c - 'a']++; // Increment the count for this character
```
- `c - 'a'`: This expression calculates the index in the `freq` array that corresponds to the character `c`.
  - `'a'` has an ASCII value of 97. So, for example:
    - If `c = 'a'`, `c - 'a'` = 0.
    - If `c = 'b'`, `c - 'a'` = 1.
    - If `c = 'h'`, `c - 'a'` = 7.
    - And so on.
- `freq[c - 'a']++`: This increments the frequency count of the corresponding character in the `freq` array.

**Example Walkthrough:**

Let's go through the input string `"hewerllo"` step by step and see how the `freq` array is updated:

- **Character 'h'**:
  - `c = 'h'`, `c - 'a' = 7`
  - `freq[7]++`: `freq` array becomes: `[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]`

- **Character 'e'**:
  - `c = 'e'`, `c - 'a' = 4`
  - `freq[4]++`: `freq` array becomes: `[0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]`

- **Character 'w'**:
  - `c = 'w'`, `c - 'a' = 22`
  - `freq[22]++`: `freq` array becomes: `[0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]`

- **Character 'e'**:
  - `c = 'e'`, `c - 'a' = 4`
  - `freq[4]++`: `freq` array becomes: `[0, 0, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]`

- **Character 'r'**:
  - `c = 'r'`, `c - 'a' = 17`
  - `freq[17]++`: `freq` array becomes: `[0, 0, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0]`

- **Character 'l'**:
  - `c = 'l'`, `c - 'a' = 11`
  - `freq[11]++`: `freq` array becomes: `[0, 0, 0, 0, 2, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0]`

- **Character 'l'** (again):
  - `c = 'l'`, `c - 'a' = 11`
  - `freq[11]++`: `freq` array becomes: `[0, 0, 0, 0, 2, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0]`

- **Character 'o'**:
  - `c = 'o'`, `c - 'a' = 14`
  - `freq[14]++`: `freq` array becomes: `[0, 0, 0, 0, 2, 0, 0, 1, 0, 0, 0, 2, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0]`

### 5. **End of Program**

```cpp
return 0;
```

This statement indicates that the program has executed successfully. In C++, returning 0 from the `main` function typically means that the program finished without errors.

### **Summary:**

- The `freq` array stores the frequency of each lowercase letter in the string `str`.
- Each index in the array corresponds to a letter ('a' to 'z'), and the value at each index indicates how many times that letter appears in the string.
- The for loop iterates through each character in the string, checking if it's a lowercase letter, and if so, increments the corresponding count in the `freq` array.

In this example, after processing the string "hewerllo", the `freq` array contains the following frequencies:

- `'h'`: 1 (at index 7)
- `'e'`: 2 (at index 4)
- `'w'`: 1 (at index 22)
-

 `'r'`: 1 (at index 17)
- `'l'`: 2 (at index 11)
- `'o'`: 1 (at index 14)

------------------

To visualize the `freq` array, we can represent it as a list with each index corresponding to a lowercase letter from 'a' to 'z'. The value at each index indicates the frequency of the corresponding letter in the input string. Here's a visual representation:

``` freq array demo
Index :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Letter: 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'
Value :  0  0  0  0  2  0  0  1  0  0  0  2  0  0  1  0  0  1  0  0  0  0  1  0  0  0
```

In this array:
- Each index corresponds to a letter of the alphabet, starting from 0 for 'a' to 25 for 'z'.
- The value at each index represents the frequency of the respective letter in the input string `"hewerllo"`.

Let's map the index to the letters and their corresponding frequencies:

- **Index 0 ('a')**: Frequency is 0
- **Index 1 ('b')**: Frequency is 0
- **Index 2 ('c')**: Frequency is 0
- **Index 3 ('d')**: Frequency is 0
- **Index 4 ('e')**: Frequency is 2
- **Index 5 ('f')**: Frequency is 0
- **Index 6 ('g')**: Frequency is 0
- **Index 7 ('h')**: Frequency is 1
- **Index 8 ('i')**: Frequency is 0
- **Index 9 ('j')**: Frequency is 0
- **Index 10 ('k')**: Frequency is 0
- **Index 11 ('l')**: Frequency is 2
- **Index 12 ('m')**: Frequency is 0
- **Index 13 ('n')**: Frequency is 0
- **Index 14 ('o')**: Frequency is 1
- **Index 15 ('p')**: Frequency is 0
- **Index 16 ('q')**: Frequency is 0
- **Index 17 ('r')**: Frequency is 1
- **Index 18 ('s')**: Frequency is 0
- **Index 19 ('t')**: Frequency is 0
- **Index 20 ('u')**: Frequency is 0
- **Index 21 ('v')**: Frequency is 0
- **Index 22 ('w')**: Frequency is 1
- **Index 23 ('x')**: Frequency is 0
- **Index 24 ('y')**: Frequency is 0
- **Index 25 ('z')**: Frequency is 0


++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

https://leetcode.com/problems/maximum-population-year/description/
https://leetcode.com/problems/count-number-of-nice-subarrays/description/






Comments

Post a Comment

Popular posts from this blog

CyberSecurity

-
 # 🔒 CYBERSECURITY A TO Z - COMPLETE GUIDE (0 to 100) # Everything You Need to Know About Cybersecurity - From Noob to Pro ================================================================================ TABLE OF CONTENTS ================================================================================ 1. CYBERSECURITY FUNDAMENTALS 2. COMMON THREATS & ATTACKS 3. AUTHENTICATION & AUTHORIZATION 4. ENCRYPTION & CRYPTOGRAPHY 5. NETWORK SECURITY 6. WEB APPLICATION SECURITY 7. DATABASE SECURITY 8. API SECURITY 9. CLOUD SECURITY 10. INCIDENT RESPONSE 11. COMPLIANCE & STANDARDS 12. SECURITY TESTING 13. SECURE CODING PRACTICES 14. DEPLOYMENT SECURITY 15. MONITORING & DETECTION 16. REAL-WORLD IMPLEMENTATIONS ================================================================================ 1. CYBERSECURITY FUNDAMENTALS ================================================================================ WHAT IS CYBERSECURITY? Protection of computer systems, networks, and data fr...
Read more

VERTICAL SCALING 💋

-
 # 🚀 VERTICAL SCALING - COMPLETE GUIDE (0 to 100) # Everything You Need to Know About Vertical Scaling in JavaScript/TypeScript ================================================================================ TABLE OF CONTENTS ================================================================================ 1. WHAT IS VERTICAL SCALING? 2. VERTICAL VS HORIZONTAL SCALING 3. NODEJS CLUSTERING 4. LOAD BALANCING 5. MEMORY OPTIMIZATION 6. CPU OPTIMIZATION 7. DATABASE OPTIMIZATION 8. CACHING STRATEGIES 9. CONNECTION POOLING 10. RATE LIMITING 11. COMPRESSION & GZIP 12. WORKER THREADS 13. MONITORING & PROFILING 14. PRODUCTION DEPLOYMENT 15. COMPLETE EXAMPLES 16. TROUBLESHOOTING ================================================================================ 1. WHAT IS VERTICAL SCALING? ================================================================================ VERTICAL SCALING (Scale Up): Increasing the power of a single server. More CPU cores, more RAM, faster storage, better ...
Read more

prisma using in project idx 13.3

-
Okay, let's troubleshoot why you might be unable to use the Prisma schema in your Project IDX workspace. Here's a breakdown of common reasons and how to fix them: 1. Prisma is not installed Problem:  Prisma might not be installed in your IDX environment. Solution:  You'll need to add it to your  .idx/dev.nix  file, like this: nix { pkgs, ... }: { # ... other configurations packages = [ # ... other packages pkgs.nodePackages.prisma ]; # ... rest of your configuration } lua (auto) Once you add this line and  rebuild the environment  by clicking the popup message, IDX will install  prisma  and make it available in your workspace. 2. The Prisma CLI is not accessible Problem:  After installation, you might need to explicitly call the Prisma CLI using its full path or use  npx . Solution:  When running Prisma commands in your terminal (in IDX), use  npx prisma  (e.g.,  npx prisma migrate dev ) or ...
Read more