Lecture22: All about Char Arrays, Strings & solving LeetCode Questions

Name: Lecture22: All about Char Arrays, Strings & solving LeetCode Questions
Uploaded: 2021-12-17T11:50:58.000Z
Duration: 3 h 46 min 20 s

Introduction to Character Arrays and Strings

Overview of the Lecture

The lecture is presented by Love Babbar, focusing on character arrays and strings in programming.

The session aims to solve numerous questions related to these topics, indicating a comprehensive exploration.

Understanding Character Variables

A character variable 'a' is introduced, initialized with the value 'z', demonstrating how single characters are stored in memory.

The limitation of character variables is highlighted; they can only store one character at a time.

Character Arrays and Strings Explained

Defining Strings

To store multiple characters like "Babbar", the concept of character arrays and strings is introduced.

In C++, a string is defined as a one-dimensional array of characters, emphasizing its structure.

Characteristics of Strings

A string consists of multiple values (characters), arranged in a one-dimensional format.

The necessity for using character arrays or strings arises from the inability of single-character variables to hold more than one character.

Practical Applications and Programming Concepts

Introduction to Crio Platform

The video mentions sponsorship by Crio, which offers project-driven programs aimed at enhancing job readiness through practical experience.

Programs Offered by Crio

Various development programs are available, including full-stack and backend development, designed for real-world application through internship-level projects.

Creating Character Arrays

Syntax for Character Arrays

To create an integer array in C++, the syntax int arr; is used. For a character array, it changes to char ch;.

Memory Representation

Each element in the character array has an index (0 through 9), similar to integer arrays. This allows traversal based on base addresses.

Inputting Data into Character Arrays

Input Methodology

Inputting data into a character array involves using cin >> name;, where 'name' represents the declared character array.

Storage Mechanism

Understanding Null Characters in C++ Input and Output

The Role of Null Characters

The input process ends with the character 'r', followed by a null character, which signifies the end of a string in memory.

The ASCII value of the null character is 0, serving as a terminator to indicate where the string concludes.

When printing strings, output will only display characters up to the null character; thus, "cout" will stop at 'r'.

Input Process Explained

During input (e.g., cin >> name), each character is stored sequentially until a null character is automatically appended after the last entered character.

For example, entering "love" results in 'l', 'o', 'v', 'e' being stored followed by a null character.

Output Behavior with Null Characters

When outputting using cout, it prints each character until it encounters a null character. Thus, for an array containing just 'a' and then a null character, only 'a' will be printed.

If multiple characters are present but separated by null characters (e.g., 'a', '0', 'b'), only the first segment before any null will be displayed.

Handling User Input

A demonstration involves creating a char array for user input. After prompting with "Enter your name", if "Babbar" is entered, it correctly displays "Your name is Babbar".

However, when entering "Love Babbar", only "Love" appears because cin stops reading at spaces.

Understanding Input Termination

The execution of cin halts upon encountering spaces, tabs (t), or newline characters (n). This means that anything following these delimiters won't be captured in the input.

Exploring Character Arrays Further

If you replace part of an array with a null character (e.g., storing "Ba0bar"), only "Ba" would print due to stopping at the first encountered null.

Understanding String Length and Reversal in C++

Finding the Length of a String

The discussion begins with an introduction to string handling in C++, focusing on how to determine the length of a string.

The example provided is the name "Babbar," which consists of 6 characters. The task is to count these characters accurately.

The counting starts from index 0, continuing until reaching the null character (0), which signifies the end of the string.

A function named getLength is proposed, where a character array (string) is passed without needing its size due to null termination.

A loop iterates through each character until it encounters the null character, incrementing a counter variable to calculate length.

Implementing and Testing String Length Function

After defining the function, it’s tested by prompting for input ("Babbar") and successfully returning its length as 6.

This confirms understanding of how strings are stored in memory and how their lengths can be calculated using simple iteration.

Reversing a String

Transitioning to reversing strings, an example with "Babbar" illustrates that the expected output should be "rabbaB."

The reversal process mirrors integer arrays; swapping elements from both ends towards the center is emphasized as straightforward logic.

A function reverse(char name[]) is introduced, utilizing two pointers: one starting at index 0 and another at n - 1.

Code Implementation for Reversal

Inside a while loop (while(s < e)), characters are swapped until both pointers meet or cross over.

Testing this reversal function with input "Babbar" yields correct results, confirming that similar logic applies across data types.

Handling Vectors for String Reversal

Discussion shifts to reversing strings represented as vectors. The same principles apply as with character arrays but adapted for vector syntax.

Emphasis on performing operations in-place without additional memory allocation aligns with efficient coding practices.

Validating Test Cases

Various test cases are run successfully, including edge cases where invalid inputs (like empty strings or single-character strings) are handled appropriately.

Final validation shows all test cases pass seamlessly, reinforcing confidence in understanding string manipulation techniques.

Checking if a String is a Palindrome

Introduction to Palindromes

What is a Palindrome?

Definition and Examples

A palindrome is defined as a string that reads the same forwards and backwards. For example, if the original string s is "abcba", its reverse rev_s will also be "abcba", confirming it as a palindrome.

The speaker illustrates this concept by stating that "car" is not a palindrome since its reverse, "rac", does not match the original. Similarly, "cat" and "Wil Babbar" are also shown to be non-palindromic examples.

Identifying Palindromes

The speaker provides an example of the word "NOON," which remains unchanged when reversed, thus qualifying it as a palindrome. This reinforces the definition provided earlier.

The discussion transitions into how to determine if a given string is a palindrome by checking for equality between the original string and its reversed version while ignoring symbols and whitespaces. This task is presented as homework for further practice.

Approaches to Check for Palindromes

First Approach: Using Extra Space

The initial method involves creating a new reversed string (reversed_s) and comparing it with the original string using a loop to check for equality, resulting in O(n) time complexity but requiring extra space for storage.

Second Approach: In-place Comparison

An alternative approach eliminates the need for additional space by comparing characters from both ends of the string towards the center:

Start with two pointers: one at the beginning (s) and one at the end (e). Compare characters at these positions.

If they are equal, move both pointers inward; if not, return false (0). This method maintains O(n) time complexity without extra space usage.

Detailed Explanation of Character Comparison

Step-by-Step Character Checking

As characters are compared:

If str[s] != str[e], return false immediately.

If they match, increment s and decrement e, continuing until all character pairs have been checked or until s exceeds e. This ensures all necessary comparisons are made efficiently without reversing strings explicitly.

Finalizing Results

Once all comparisons are complete without mismatches, it confirms that the input string is indeed a palindrome. The function designed to check this can be implemented succinctly in code form using boolean returns based on character comparisons throughout iterations.

Practical Implementation Example

Testing with User Input

A practical demonstration involves prompting users to enter their names:

When tested with various inputs like "Babbar" (not palindromic) versus "NooN" (palindromic), results confirm whether each name meets palindromic criteria based on case sensitivity during comparison processes.

Understanding Palindromes and Case Sensitivity

Logic for Checking Palindromes

The logic for determining if a string is a palindrome involves using two pointers: one at the start and one at the end of the string. If characters match, move inward; if they don't, it's not a palindrome.

The process requires careful reading of the question to understand how case sensitivity affects palindrome checks. Uppercase and lowercase letters are treated differently in some implementations.

Criteria for Valid Characters

Only alphanumeric characters (a-z, 0-9) should be considered valid when checking for palindromes. Special characters and whitespace are ignored.

It's essential to treat uppercase and lowercase letters as equivalent when checking for palindromes, which means converting all characters to a common case.

Converting Characters to Lowercase

To ensure case insensitivity, implement a function that converts any character to lowercase before comparison. This can be done by checking if the character is already in lowercase or converting it if it's uppercase.

The conversion logic involves subtracting 'A' from an uppercase character and adding 'a' to get its lowercase equivalent.

Understanding ASCII Values

The method relies on understanding ASCII values: subtracting 'A' from an uppercase letter gives you its position relative to 'a'.

For example, converting 'B' (ASCII 66) involves calculating its difference with 'A' (ASCII 65), then adding 'a' (ASCII 97).

Converting Numeric Characters

To convert numeric characters like '1' into their integer form, simply subtract the ASCII value of '0'. This approach applies consistently across different types of character conversions.

Understanding Palindromes and String Manipulation

Case Sensitivity in Palindrome Checking

The process begins by converting characters to lowercase before comparison, ensuring case insensitivity. For example, the word "Noon" is now recognized as a palindrome.

Analyzing Simple Examples

A simple example is introduced: "A1b22Ba". This serves as a basis for understanding how to identify palindromes through character comparison.

Steps to Determine Palindrome Status

The method involves comparing characters from both ends of the string. If any pair does not match, it confirms that the string is not a palindrome.

Handling Non-Alphanumeric Characters

Only numbers and letters are considered; special characters and whitespaces are ignored during comparisons. This adds complexity but ensures accurate palindrome checks.

Homework Assignment on Validating Palindromes

Viewers are assigned homework to implement a function that checks if a string is a valid palindrome after normalizing it (lowercase conversion and removal of non-alphanumeric characters).

Exploring C++ Strings

Introduction to C++ String Class

The discussion shifts towards understanding strings in C++. A string is defined as a class type, similar to character arrays but with additional functionalities.

Creating Strings in C++

To create a string, one can declare it using string s; or initialize it with values like string str = "Babbar";.

Memory Representation of Strings

Internally, strings consist of their characters followed by a null terminator (0). This representation mirrors that of character arrays.

Built-in Functions for String Manipulation

Various functions such as str.length() for length retrieval and str.push_back('c') for adding characters are discussed. These enhance usability compared to basic character arrays.

Additional String Operations

Functions like pop_back() remove the last character from the string. Other operations include finding substrings and comparing strings using built-in methods.

Differences Between Character Arrays and Strings

Key Differences Highlighted

Understanding String Manipulation and Palindrome Checking

Homework Assignment on String Output

The instructor emphasizes the importance of comparing outputs from a string containing characters like 'a', 'b', '0', 'c', and 'd'. Students are tasked with analyzing differences in outputs as homework.

Valid Palindrome Process

The next topic is about checking for valid palindromes, which involves removing unnecessary characters, converting all letters to lowercase, and then verifying if the string reads the same forwards and backwards.

Algorithm Development for Character Validation

A loop is introduced where an index 'i' will traverse through the string to identify valid characters (a-z, A-Z, 0-9).

If a character is valid, it will be swapped with another index 'j' to build a new string without invalid characters.

Steps for Implementing Palindrome Check

The algorithm consists of three main steps: remove useless characters, convert to lowercase, and check if it's a palindrome.

Useless characters are defined as anything outside alphanumeric ranges.

Function Creation for Valid Characters

A function bool valid(char ch) checks if a character falls within acceptable ranges (lowercase letters, uppercase letters, digits).

Building the Final Code Structure

Loop Implementation for Character Filtering

A loop iterates through each character in the original string; valid ones are pushed into a temporary string while ignoring invalid ones.

Lowercase Conversion Functionality

After filtering out invalid characters, there's a need to convert remaining characters to lowercase using an established function.

Finalizing Palindrome Check Logic

The final step involves invoking an existing palindrome-checking function after ensuring all conditions have been met regarding case sensitivity and character validity.

Testing Edge Cases in Code

Dynamic Test Cases Evaluation

Various test cases are run including empty strings and strings with only spaces or single characters. These edge cases help ensure robustness in handling different inputs.

Introduction to New Problem: Reverse Words in a String

Overview of Reversing Words Challenge

The next challenge involves reversing words within a given input while maintaining whitespace positions. An example illustrates this concept clearly.

Approach Explanation for Word Reversal

When encountering spaces during traversal of the input string, completed words should be reversed immediately. Special attention is given to handle cases where no space follows the last word.

Next Topic: Maximum Occurring Character

Transitioning to New Problem Statement

Character Frequency Analysis in Strings

Introduction to the Problem

The task involves determining which character occurs the most frequently in a given string, using "test" as an example where 't' appears twice, while 'e' and 's' appear once.

Coding Approach

The coding process begins with reading a string input using cin >> s; to prepare for analysis.

A function named getMaxOccurringCharacter() is defined to encapsulate the logic for finding the maximum occurring character.

Understanding Constraints

The constraints specify that the string length can be up to 100 characters and will only contain alphabetic characters (a-z or A-Z).

An array of size 26 is proposed to count occurrences, treating uppercase and lowercase letters equivalently by mapping them from 'a' (0) to 'z' (25).

Counting Logic

For each character, if it’s lowercase, subtracting 'a' gives its index; for uppercase characters, subtracting 'A' achieves the same result.

An integer array initialized with zeros will store counts of each character as they are encountered during traversal of the string.

Traversal and Count Update

A loop iterates through each character in the string. If it's within lowercase bounds ('a'-'z'), it updates its corresponding count in the array.

In case of uppercase letters, similar logic applies but uses subtraction from 'A'.

Finding Maximum Occurrence

After populating counts, another loop traverses through the count array to find the maximum value and its corresponding index.

If a new maximum is found (maxi < arr[i]), it updates both ans (the answer variable storing index of max char) and maxi.

Finalizing Results

The final answer is derived by converting the index back into a character using char finalAns = 'a' + ans;.

Testing Functionality

Initial tests are conducted with inputs like "test", yielding expected results such as returning 't'.

Code Optimization Insights

Observations reveal that unnecessary checks were included based on assumptions about input constraints which could be simplified.

Conclusion on Implementation

The approach effectively utilizes an indexed counting method for characters while ensuring clarity in code structure.

Character Count and Maximum Occurrence in a String

Understanding Character Mapping and Counting

The discussion begins with mapping characters to their respective indices, where 'a' is 0, 'b' is 1, and so forth. Each character's occurrence count is stored in an array.

The maximum occurrence of any character can be easily identified; for example, if 'f' occurs three times, it is noted as the maximum.

The process involves creating an array from the string to track counts, finding the maximum index, and returning the corresponding character.

Complexity Analysis

Time complexity is analyzed: the first loop runs O(n), where n is the length of the string. A second constant-time loop runs O(1).

Space complexity remains constant at O(1), given that only a fixed-size array (26 elements for each letter) is used.

Input Handling Techniques

Managing Input with cin

It’s explained that cin stops reading input upon encountering spaces or newline characters.

To read an entire line including spaces, cin.getline should be used along with specifying a character array name and its length.

Custom Delimiters

For custom delimiters in input handling, users are encouraged to search online for implementation techniques as part of their homework.

String Operations Using Built-in Functions

Length Calculation and Comparison

To find a string's length in C++, one can use strlen(name) for character arrays or .length() method for strings.

String comparison can be performed using strcmp(s1 , s2) which returns non-zero if strings are not equal.

Copying Strings

Strings can be copied using strcpy(destination, source) or through assignment like st = s1.

Removing Spaces from Strings

Problem Statement

The task involves replacing all spaces in a given string with '@40', transforming "My name is KHAN" into "My@40name@40is@40KHAN".

Implementation Steps

A temporary string (temp) will store results while iterating through the original string.

If a space is encountered during iteration (if ( s[i] == ' ')), it gets replaced by '@40'; otherwise, the current character gets appended to temp.

Final Execution

Homework Assignment and In-Place String Modification

Understanding the Homework Task

The instructor assigns homework focused on modifying a string in place without using extra space, emphasizing that changes should be made directly to the original 'str' string.

The requirement is for an O(1) space solution, with time complexity being O(n), where n is the length of the string. A new string named 'temp' would lead to O(n) space complexity.

Removing Substrings from a String

The next task involves removing all occurrences of a substring ('part') from a main string ('s'). This requires repeated operations until no instances of 'part' remain.

A substring is defined as continuous sequences of characters within a string. The goal is to find and remove every occurrence of 'part'.

Example Walkthrough

An example illustrates how to remove occurrences: starting with "d a a b c b a a b c b c" and removing "abc" results in "d a b".

After multiple removals, the final answer becomes "dab", demonstrating the process clearly.

Implementation Strategy

Constraints indicate that the maximum length for strings is 1000. The approach involves traversing while checking if 'part' exists in 's'.

Functions like find (to locate substrings) and erase (to remove them) are essential tools for this implementation.

Code Execution Insights

If no return value is provided after deletion attempts, errors will occur. Proper checks ensure that when 'part' is not found, the loop exits correctly.

The logic implemented checks if 'part' exists in 's', deleting it iteratively until none remains.

Permutation Check Between Two Strings

Problem Definition

The next question focuses on determining if one string (s1's permutation) exists as a substring within another string (s2).

Example Clarification

For instance, given s2 = "e i d b a o o o" and s1 = "ab", valid permutations include both "ab" and "ba". Finding either confirms success.

Key Conditions for Validity

It's crucial that permutations must appear continuously; separate characters do not count towards forming valid permutations.

Approach Outline

To solve this problem, character counts from s1 are stored similarly to previous exercises using an array indexed by character values.

Sliding Window Technique

Understanding Character Count and Window Traversal

Initial Setup and Character Counting

The process begins by checking if a string is a permutation, leading to the storage of character counts in an array s1 for later comparison.

A window traversal approach is introduced, where characters not present in the target string are identified as irrelevant, prompting adjustments to the count.

Emphasis on maintaining a constant size for character comparisons due to the limited number of characters (26), making it manageable and efficient.

Implementing Character Count Array

An integer array count is initialized to store character frequencies, starting with all values set to zero.

The index for each character is calculated using int index = s1[i] - 'a', simplifying access to the count array.

Window Traversal Logic

A sliding window mechanism is established with a size equal to that of s1, allowing traversal through another string s2.

The first window's setup involves initializing variables and preparing for subsequent iterations over the string.

Comparing Character Counts

After processing the first window, a check between two count arrays (count1 and count2) determines if they match; if true, it returns success.

If counts differ, further processing occurs by continuing through additional windows until all possibilities are explored.

Adjusting Counts During Traversal

As new elements enter or exit the current window during traversal, their respective counts are adjusted accordingly—incrementing for new entries and decrementing for those leaving.

The old character exiting the window is identified using its index derived from its position relative to k, ensuring accurate updates in counts.

Final Checks and Execution

Continuous checks ensure that after every adjustment of counts, equality between both count arrays is verified before proceeding further.

Understanding String Manipulation and Complexity

Initial Problem Encounter

The speaker discusses a case where the string length is one, indicating that any character not present in it should be handled correctly. A runtime error occurs during submission, suggesting a mistake was made.

Analyzing Window Logic

The speaker explains finding the index of characters in the second string (s2) and how to manage windows while iterating through them. They emphasize checking conditions to avoid exceeding the string's length.

Count Array Comparison

A count array for the first string (s1) is created to track character occurrences. The second string's first window is checked against this count array for equality.

Sliding Window Technique

If the count arrays are unequal, the speaker describes moving to the next window by removing the leftmost character and adding a new one, reiterating this process until all windows are checked.

Time and Space Complexity Analysis

The overall time complexity is discussed as O(m + n), where m is the length of s1 and n is that of s2. Space complexity remains constant at O(26), accounting for fixed character counts.

Removing Adjacent Duplicates

Problem Introduction

The next question involves removing adjacent duplicate characters from strings, with examples provided such as "abdaca" leading to "ca".

Step-by-Step Example Walkthrough

For input "azxxzy", duplicates are removed stepwise until reaching "ay". This illustrates how duplicates can be eliminated iteratively.

Homework Assignment

The speaker assigns this problem as homework, encouraging viewers to attempt solving it independently before seeking help or solutions.

String Compression Challenge

Understanding Input and Output Requirements

In discussing string compression, an example input like "a,a,b.b.b.c.c.c" leads to output reflecting counts of each character (e.g., "a,2").

Understanding Character Count and Output Formatting

Overview of the Counting Process

The process involves counting how many times each character appears in a given input, with specific rules for output formatting based on the count.

If a character appears only once, it is displayed without any count; for example, 'b' would simply be written as 'b'.

Characters that appear more than once are formatted to include their counts (e.g., 'a' appearing twice would be represented as 'a2').

Handling Counts Greater Than One

For characters with counts greater than one, if the count is a single digit (less than 10), it is displayed directly alongside the character.

If the count exceeds 9, it must be converted into individual digits before being appended to the output (e.g., a count of 12 becomes '1' and '2').

Algorithm Creation and Implementation

The algorithm requires careful tracking of characters and their counts while ensuring that only valid outputs are stored in an answer array.

It emphasizes not using separate storage for answers but rather incorporating them directly into a designated vector or array.

Looping Through Characters

A loop iterates through each character in the input string, comparing adjacent characters to determine if they are identical.

When encountering a different character or reaching the end of the string, it stores the previous character's information before moving on.

Storing Results Based on Conditions

Upon exiting the comparison loop, results are stored based on whether counts exceed one; this includes converting counts to strings when necessary.

Understanding Character Counting Logic

Overview of the Solution

The logic involves converting a character counting process into a single digit format, which simplifies the overall approach without being noticed by others.

The first character is saved along with its count, allowing for a transition to the next character when identified at index j, indicating that i will now equal j.

Output and Functionality

The output of the function includes returning the size of the answer array, which was previously tracked using an index.

After running all test cases successfully, it confirms that the solution works effectively and has improved accuracy.

Detailed Explanation of Steps

A variable l is initialized to traverse through the vector while maintaining an index (ans) to track valid entries.

A while loop increments j as long as identical characters are encountered; exiting this loop indicates a new character has been found.

Final Thoughts on Implementation

The solution concludes with a recap of how many questions were addressed in this session. It notes that it's early morning and emphasizes dedication despite fatigue.

Complexity Analysis

The space complexity is constant (O(1)), as no extra space was utilized beyond necessary variables.

Time complexity is linear (O(N)), attributed to traversing through the vector once with only one while loop involved.

Additional Resources and Feedback Request