Skip to main content

DSA String Cheat Sheet


Difference between substring and subsequence ?

substring is continuous, while subsequence is not continuous  


1. Longest Palindrome Substring - example -  ababd

Approach

1. Brute force -  create all the substring, so create the substring of length 1 , length 2 , length 3, length 4 , and length 5. and then check for the string that has the maximum length . 

Time complexity is O(N^3) 


2. Decision Tree - 

 return max(count,
        max(longestPalindromic(str, i + 1, j, 0),
longestPalindromic(str, i, j - 1, 0)));



3. Dynamic programming using the TABULAR Approach  


for d = 0; d < noOfRowSize; d++  // Row major 

    for i =0, j = d; i < noOfRowsSize, j < noOfColumnsSize ; i++ , j++

        if (i == j || d i.e. Diagonal is Zero ) // that means they are equal

            DP[i][j] = 1

            MAX = 1 

        else if( j - 1 == 1) // length diff is ONE

            if(ARR[i] == ARR[j])

                DP[i][j] = 1

                MAX = 2

        else

            if( ARR[i] == ARR[j]  && DP[i+1][j-1] == 1  )

                DP[i][j] = 1 

                MAX = j - 1 + 1         


How to calculate the MAX length 


4. Expand from middle

Row Major & Column Major iteration 


Diagonal iteration -  

for d = 0; d < noOfRowSize; d++

    for i =0, j = d;  j < noOfColumnsSize ; i++ , j++

        


2. Longest Palindrome Subsequence 


Pattern Matching Algorithm

0. Brute force or Naïve Search , String matching algorithm.  

1. Rabin Karp algorithm is an pattern matching or the search algorithm, using the hashing algorithm. 

Algo - 

a. We need to assign an numerical value to each character, in this case we can use the ACSCII value for each character.

b. Hash Function (why this hash function or the spurious value - The reason is collision , hence we are multiplying the value with 10, to avoid the collision)  

hash value for pattern(p) = Σ(value * pow(10, position) )

example 

pattern = abc

text = xyzabc

suppose the value for a = 1, b = 2, c = 3

then the pattern value would be 

(a * 10 ^ 2) + (b * 10 ^ 1) + (c * 10 ^ 0)

which means

(1 * 10 ^ 2) + (2 * 10 ^ 1) + (3 * 10) = 100 + 20 + 3 = 123


c. Sliding window logic so that we don't recompute the value again 

d. comparison 


2. KMP Algorithm 


3. Z - Algorithm 

text = "batsdjfkljsljdfklsjkldjlfkjsldjbat"  pattern = "bat"




Implement ATOI function

ATOI is an function in the C programming language that converts a string into an integer numerical representation.

1. check if the first character is minus, then toggle on the flag

2. Java trick to get the ASCII value (int)str.getCharAt(1) , will return the integer or the numerical value , if the int value is in between 0 and 9 then process else skip the loop

3. Now how to compute, the very old trick 

 ASCII Value (NUMBER) -  ASCII Value(0) will return the integer 

multiply each integer with the Power of 10 ^ n , incrementally in every loop   and then SUM 


Longest Common Prefix

1. The easiest solution is BRUTE Force algorithm 

Complexity - O(No of Strings * length of shortest string) 

2. TRIE implementation


Longest Common Subsequence 


1. using recursion 

2. DP






   

Comments

Post a Comment

Popular posts from this blog

Hexagonal Architecture (Ports & Adapters Pattern)

Hexagonal Architecture , also known as the Ports and Adapters pattern, is a software design pattern that aims to create a decoupled and maintainable application by separating the core business logic from external concerns (like databases, APIs, and UIs). Structure of Hexagonal Architecture A typical Hexagonal Architecture has three main layers: 1️⃣ Core Domain (Application Logic) This contains the business rules and domain models. It is completely independent of external technologies . Example: If you’re building a banking system , this part would include logic for transactions, withdrawals, and deposits . 2️⃣ Ports (Interfaces) These are interfaces that define how the core interacts with external components. Two types of ports: Inbound Ports (driven by external inputs like APIs, UI, or events) Outbound Ports (used to interact with external services like databases, messaging systems, etc.) 3️⃣ Adapters (Implementation of Ports) These are concrete implementations of the ports, re...
Post a Comment
Read more

"Action-Oriented, Stakeholder-Focused" MoM Structure

  I. Meeting Header: Meeting Title:  Clear and concise (e.g., "Project X Status Update," "Q3 Planning Meeting"). Date and Time:  Record the date and time the meeting took place. Location/Platform:  Indicate where the meeting was held (e.g., Conference Room A, Zoom). Attendees:  List the names and roles of everyone who attended. Absent:  List the names of key individuals who were invited but did not attend. Meeting Owner : Who was in charge of the meeting ? Document owner : Who is in charge of the documentation ? II. Key Discussion Points (Concise Summary): Purpose:  Briefly summarize the main topics discussed. Format:  Use bullet points for brevity. Content: Decision Points:  Clearly state any decisions that were made. Key Information:  Summarize any crucial information shared. Key Questions : Summarize the key questions that were raised. Open Issues:  Note any issues that remain unresolved. Stakeholder Focus:  Frame the summar...
Post a Comment
Read more

Frameworks

  I. Frameworks for All Roles (Tech Lead, VP, Individual Contributor): Communication Frameworks: BLUF (Bottom Line Up Front):  For concise and effective communication, especially in emails and reports. SCQA (Situation, Complication, Question, Answer):  For structuring business communications and presentations to present a clear narrative. PAS (Problem, Agitation, Solution):  For a persuasive message. BAB (Before, After, Bridge):  For a persuasive message with a focus on the future. Sparkline:  For persuasive presentation with a focus on change. STAR (Situation, Task, Action, Result):  For structuring behavioral stories, particularly in interviews or performance reviews. Problem-Solving/Decision-Making Frameworks: 5 Whys:  For root cause analysis. Systems Thinking:  For understanding complex systems. The Four Questions:  For a post mortem. Human Factors : For a blame less post mortem. Time Management/Prioritization Frameworks: Eisenhower ...
Post a Comment
Read more