## Understanding Character Encoding

Ever imagined how a computer is able to understand and display what you have written? Ever wondered what a UTF-8 or UTF-16 meant when you were going through some configurations? Just think about how “HeLLo WorlD” should be interpreted by a computer.
We all know that a computer stores data in bits and bytes. So, to display a character on screen or map the character as a byte in memory of the computer needs to have a standard. Read the following :

`\x48\x65\x4C\x4C\x6F\x20\x57\x6F\x72\x6C\x44`

This is something a memory would show you. How do you know what character each memory byte specifies?

Here comes character encoding into the picture:

If you have already not guessed it – Its “HeLLo WorlD” in UTF-8 for you. And yes, we will go ahead and read about UTF-8. But let’s start with ASCII. Most of you who have done programming or worked with strings must have known what ASCII is. If you haven’t then let’s define what ASCII is.
ASCII: ASCII stands for American Standard Code for Information Interchange. Computers can only understand numbers, so an ASCII code is the numerical representation of a character such as ‘a’ or ‘@’ or an action of some sort. ASCII was developed a long time ago and now the non-printing characters are rarely used for their original purpose.

Just look at the following –

\x48 110 H
\x65 145 e
\x4c 114 L

And so on.  If you have not already looked at the table, I will recommend that you do it now! You will observe that these are a simple set of English words and punctuations.

Now Suppose I want to write the below characters:

A
B?@

This will be interpreted by my decoder as 0x410x0a0x200x420x3f0x40 in hex and 065010032066063064 in decimal, where even a space (0x20) and a next line (0x0a) has a byte value or a memory space.

Different countries, languages but the need that brought them together

Today internet has made the world come close together. And the people all over the world do not speak just English, right? There came a need to expand this space. If you have created an application and you see that people in France want to use it as you see a high potential there. Wouldn’t it be nice to just have a change in language but having the same functionality?

Why not create a Universal Code in short Unicode for everyone ??

So, here came the Unicode with a really good idea. It assigned every character, including different languages, a unique number called Code Point. One advantage of Unicode over other possible sets is that its first 256 code points are identical to ASCII. So for a software/browser it is easier to encode and decode characters of majority of living languages in use on computers. It aims to be, and to a large extent already is, a superset of all other character sets that have been encoded.

Ref: http://www.w3.org/

Unicode also is a character set (not an encoding). It uses the same characters like the ASCII standard, but it extends the list with additional characters, which gives each character a Code point. It has the ambition to contain all characters (and popular icons) used in the entire world.

Before knowing these let us get a few terminologies straight :

• A character is a minimal unit of text that has semantic value.
• A character set is a collection of characters that might be used by multiple languages. Example: The Latin character set is used by English and most European languages, though the Greek character set is used only by the Greek language.
• A coded character set is a character set in which each character corresponds to a unique number.
• A code point of a coded character set is any legal value in the character set.
• A code unit is a bit sequence used to encode each character of a repertoire within a given encoding form.

Ever wondered what is UTF-8 or UTF-16??

UTF-8: UTF-8 has truly been the dominant character encoding for the World Wide Web since 2009, and as of June 2017 accounts for 89.4% of all Web pages. UTF-8 encodes each of the 1,112,064 valid code points in Unicode using one to four 8-bit bytes. Code points with lower numerical values, which tend to occur more frequently, are encoded using fewer bytes. The first 128 characters of Unicode, which correspond one-to-one with ASCII, are encoded using a single octet with the same binary value as ASCII, so that valid ASCII text is valid UTF-8-encoded Unicode as well.

So how many bytes give access to what characters in these encodings?
UTF-8:
1 byte: Standard ASCII
2 bytes: Arabic, Hebrew, most European scripts (most notably excluding Georgian)
3 bytes: BMP
4 bytes: All Unicode characters

UTF-16:
2 bytes: BMP
4 bytes: All Unicode characters

So I did make a mention about BMP. What is it exactly?

Basic Multilingual Plane (BMP) contains characters for almost all modern languages, and a large number of symbols. A primary objective for the BMP is to support the unification of prior character sets as well as characters for writing.

Ref: http://www.w3.org/

UTF-8, UTF-16 and UTF-32 are encodings that apply the Unicode character table. But they each have a slightly different way on how to encode them. UTF-8 will only use 1 byte when encoding an ASCII character, giving the same output as any other ASCII encoding. But for other characters, it will use the first bit to indicate that a 2nd byte will follow. UTF-16 uses 16-bit by default, but that only gives you 65k possible characters, which is nowhere near enough for the full Unicode set. So some characters use pairs of 16-bit values. UTF-32 is opposite, it uses the most memory (each character is a fixed 4 bytes wide), which makes it quite bloated but now in this scenario every character has this precise length, so string manipulation becomes far simpler. You can compute the number of characters in a string simply from the length in bytes of the string. You can’t do that with UTF-8.This is how it eases to accommodate the entire character set for different languages and help people spread their applications or information to the world just coding/writing in their language rest all is taken care by the Decoder.

As this being just the beginning into the world of Character Encoding. I hope this helps you understand Character encoding at a higher level.

## Arrays in JavaScript

In JavaScript, array is a single variable that is used to store different elements. It is often used when we want to store list of elements and access them by a single variable. Unlike most languages where array is a reference to the multiple variable, in JavaScript array is a single variable that stores multiple elements.

Declaration of an Array
There are basically two ways to declare an array.
Example:

But generally method 1 is preferred over the method 2. Let us understand the reason for this.

Initialization of an Array
Example (for Method 1):

Example (for Method 2):

As shown in above example the house contains 5 elements i.e. (10 , 20, 30, 40, 50)while house1 contains 5 undefined elements instead of having a single element 5. Hence, while working with numbers this method is generally not preferred but it works fine with Strings and Boolean as shown in the example above home contains a single element 1BHK.

An array in JavaScript can hold different elements
We can store Numbers, Strings and Boolean in a single array.
Example:

Accessing Array Elements
Array in JavaScript are indexed from 0 so we can access array elements as follows:

Length property of an Array
Length property of an Array returns the length of an Array. Length of an Array is always one more than the highest index of an Array.
Example below illustrates the length property of an Array:

Note : All the above examples can be tested by typing them within the script tag of HTML

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/arrays-in-javascript/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Closure in JavaScript

Most of the JavaScript Developers use closure consciously or unconsciously. Even if they do unconsciously it works fine in most of the cases. But knowing closure will provide a better control over the code when using them. And another reason for learning closure is that it is the most frequently asked question in the interview for the JavaScript developers.

Let’s see and understand closure through an example.
Example 1:

`// Explaination of closure`
`/* 1 */``function foo()`
`/* 2 */``{`
`/* 3 */``var b = ``1``;`
`/* 4 */``function inner(){`
`/* 5 */``return``b;`
`/* 6 */``}`
`/* 7 */``return``n;`
`/* 8 */``}`
`/* 9 */``var get_func_inner = foo();         `
`/* 10 */``console.log(get_func_n());`
`/* 11 */``console.log(get_func_n());`
`/* 12 */``console.log(get_func_n());`

Explanation:Interesting thing to note here is from line number 9 to line number 12 . At line number 9 we are done with the execution of function foo() but we can access the variable which is defined in function foo() through function inner() i.e in line number 10, 11, 12. and as desired it logs the value of b. This is closure in action that is inner function can have access to the outer function variables as well as all the global variables.
Output of the above code:

In order to see the variable and function bound within closure we can write as:

`/* 13 */``console.dir(get_func_inner);`

Output:

As we can see the variables within the closure in the scope section.

Definition of Closure:

In programming languages, closures (also lexical closures or function closures) are techniques for implementing lexically scoped name binding in languages with first-class functions. Operationally, a closure is a record storing a function[a] together with an environment:[1] a mapping associating each free variable of the function (variables that are used locally, but defined in an enclosing scope) with the value or reference to which the name was bound when the closure was created.[b]
-Wikipedia

or

In other words, closure is created when a child function keep the environment of the parent scope even after the parent function has already executed

Now lets look at the another example.
Example 2:

`function foo(outer_arg) {`
`    ``function inner(inner_arg) {`
`        ``return``outer_arg + inner_arg;`
`    ``}`
`    ``return``inner;`
`}`
`var get_func_inner = foo(``5``);`
`console.log(get_func_inner(``4``));`
`console.log(get_func_inner(``3``));`

Explanation: In the above example we used a parameter function rather than a default one. Note even when we are done with the execution of foo(5) we can access the outer_arg variable from the inner function. And on execution of inner function produce the summation of outer_arg and inner_arg as desired.
Output:

Now let’s see an example of closure within a loop.
In this example we would to store a anonymous function at every index of an array.
Example 3:

`// Outer function`
`function outer() `
`{`
`    ``var arr = [];`
`    ``var i;`
`    ``for``(i = ``0``; i < ``4``; i++) `
`    ``{`
`        ``// storing anonymus function`
`        ``arr[i] = function () { ``return``i; }`
`    ``}`
`    ``// returning the array.`
`    ``return``arr;`
`}`
`var get_arr = outer();`
`console.log(get_arr[``0``]());`
`console.log(get_arr[``1``]());`
`console.log(get_arr[``2``]());`
`console.log(get_arr[``3``]());`

Output:

Explanation: Did you guess the right answer? In the above code we have created four closure which point to the variable i which is local variable to the function outer.Closure don’t remember the value of the variable it only points to the variable or stores the reference of the variable and hence, returns the current value. In the above code when we try to update the value of it gets reflected to all because the closure stores the reference.
Lets see an correct way to write the above code so as to get different values of i at different index.
Example 4:

`// Outer function`
`function outer() `
`{`
`    ``function create_Closure(val) `
`    ``{`
`        ``return``function() `
`        ``{`
`            ``return``val;`
`        ``}`
`    ``}`
`    ``var arr = [];`
`    ``var i;`
`    ``for``(i = ``0``; i < ``4``; i++) `
`    ``{`
`        ``arr[i] = create_Closure(i);`
`    ``}`
`    ``return``arr;`
`}`
`var get_arr = outer();`
`console.log(get_arr[``0``]());`
`console.log(get_arr[``1``]());`
`console.log(get_arr[``2``]());`
`console.log(get_arr[``3``]());`

Ouput:

Explanation: In the above code we are updating the argument of the function create_Closure with every call. Hence, we get different values of i at different index.

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/closure-in-javascript/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Representation of a number in powers of other

Given two numbers w and m, we need to determine whether it is possible to represent m in terms of powers of w. The powers of number w can be added or subtracted to obtain m and each powers of w can be used only once .

Examples:

```Input : 3 7
Output : Yes
As 7 = 9 - 3 + 1 (3^2 - 3^1 + 3^0 )
so it is possible .

Input : 100 50
Output : No
As 50 is less than 100 so we can never
represent it in the powers of 100 .```

Here we have to represent m in terms of powers of w used only once so it can be shown through the following equation .
c0 + c1*w^1 + c2*w^2 + … = m —— (Equation 1)

Where each c0, c1, c2 … are either -1 (for subtracting that power of w ), 0 (not using that power of w ), 1 (for adding that power of w ) .

=> c1*w^1 + c2*w^2 + … = m – c0
=> w(c1 + c2*w^1 + c3*w^2 + … ) = m – c0
=> c1 + c2*w^1 + c3*w^2 + … = (m – c0)/w —— (Equation 2)

Now, notice equation 1 and equation 2 — we are trying to solve the same problem all over again. So we have to recurse till m > 0 . For such a solution to exist (m — ci) must be a multiple of w, where ci is the coefficient of the equation . The ci can be -1, 0, 1 . So we have to check for all three possibilities ( ( m – 1 ) % w == 0), ( ( m + 1 ) % w == 0) and ( m % w == 0) . If it is not, then there will not be any solution.

`// CPP program to check if m can be represented`
`// as powers of w.`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`bool` `asPowerSum(``int` `w, ``int` `m)`
`{`
`    ``while` `(m) {`
`        ``if` `((m - 1) % w == 0) `
`            ``m = (m - 1) / w;`
`       ``else` `if` `((m + 1) % w == 0) `
`            ``m = (m + 1) / w;`
`        `
`        ``else` `if` `(m % w == 0) `
`            ``m = m / w;`
`        `
`        ``else`
`            ``break``; ``// None of 3 worked.`
`    ``}`
`    ``// If m is not zero means, it can't be `
`    ``// represented in terms of powers of w.`
`    ``return` `(m == 0);`
`}`
`// Driver code`
`int` `main()`
`{`
`    ``int` `w = 3, m = 7;`
`    ``if` `(asPowerSum(w, m))`
`        ``cout << ``"Yes"` `<< endl;`
`    ``else`
`        ``cout << ``"No"` `<< endl;`
`   ``return` `0;`
`}`

Output:

```Yes

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/representation-number-powers/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Print Number series without using any loop

Problem – Givens Two number N and K, our task is to subtract a number K from N until number(N) is greater than zero, once the N becomes negative or zero then we start adding K until that number become the original number(N).
Note : Not allow to use any loop.

Examples :

```Input : N = 15 K = 5
Output : 15 10 5 0 1 5 10 15

Input : N = 20 K = 6
Output : 20 14 8 2 -4 2 8 14 20
```

Explanation – We can do it using recursion idea is that we call the function again and again until N is greater than zero (in every function call we subtract N by K). Once the number becomes negative or zero we start adding K in every function call until the number becomes the original number. Here we use a single function for both addition and subtraction but to switch between addition or subtraction function we used a Boolean flag.

Code –

`// C++ program to Print Number`
`// series without using loop`
`#include <iostream>`
`using` `namespace` `std;`
`// function print series`
`// using recursion`
`void` `PrintNumber(``int` `N, ``int` `Original, ``int` `K, ``bool` `flag)`
`{`
`    ``// print the number`
`    ``cout << N << ``" "``;`
`    ``// change flag if number`
`    ``// become negative`
`    ``if` `(N <= 0)`
`        ``flag = !flag;`
`    ``// base condition for`
`    ``// second_case (Adding K)`
`    ``if` `(N == Original && !flag)`
`        ``return``;`
`    ``// if flag is true`
`    ``// we subtract value until`
`    ``// number is greater then zero`
`    ``if` `(flag == ``true``) {`
`        ``PrintNumber(N - K, Original, K, flag);`
`        ``return``;`
`    ``}`
`    ``// second case (Addition )`
`    ``if` `(!flag) {`
`        ``PrintNumber(N + K, Original, K, flag);`
`        ``return``;`
`    ``}`
`}`
`// driver program`
`int` `main()`
`{`
`    ``int` `N = 20, K = 6;`
`    ``PrintNumber(N, N, K, ``true``);`
`    ``return` `0;`
`}`

Output :

```20 14 8 2 -4 2 8 14 20

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/print-number-series-without-using-loop/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Print all subsequences of a string | Iterative Method

Given a string s, print all possible subsequences of the given string in an iterative manner.
Examples:

```Input : abc
Output : a, b, c, ab, ac, bc, abc

Input : aab
Output : a, b, aa, ab, aab```

We use bit pattern from binary representation of 1 to 2^length(s) – 1.

input = “abc”
Binary representation to consider 1 to (2^3-1), i.e 1 to 7.
Start from left (MSB) to right (LSB) of binary representation and append characters from input string which corresponds to bit value 1 in binary representation to Final subsequence string sub.

Example:
001 => abc . Only c corresponds to bit 1. So, subsequence = c.
101 => abc . a and c corresponds to bit 1. So, subsequence = ac.

binary_representation (1) = 001 => c
binary_representation (2) = 010 => b
binary_representation (3) = 011 => bc
binary_representation (4) = 100 => a
binary_representation (5) = 101 => ac
binary_representation (6) = 110 => ab
binary_representation (7) = 111 => abc

Below is the implementation of above approach:

`// CPP program to print all Subsequences`
`// of a string in iterative manner`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`// function to find subsequence`
`string subsequence(string s, ``int` `binary, ``int` `len)`
`{`
`    ``string sub = ``""``;`
`    ``for` `(``int` `j = 0; j < len; j++)`
`        ``// check if jth bit in binary is 1`
`        ``if` `(binary & (1 << j))`
`            ``// if jth bit is 1, include it`
`            ``// in subsequence`
`            ``sub += s[j];`
`    ``return` `sub;`
`}`
`// function to print all subsequences`
`void` `possibleSubsequences(string s){`
`    ``// map to store subsequence `
`    ``// lexicographically by length`
`    ``map<``int``, set<string> > sorted_subsequence;`
`    ``int` `len = s.size();`
`    `
`    ``// Total number of non-empty subsequence`
`    ``// in string is 2^len-1`
`    ``int` `limit = ``pow``(2, len);`
`    `
`    ``// i=0, corresponds to empty subsequence`
`    ``for` `(``int` `i = 1; i <= limit - 1; i++) { `
`        `
`        ``// subsequence for binary pattern i`
`        ``string sub = subsequence(s, i, len);`
`        `
`        ``// storing sub in map`
`        ``sorted_subsequence[sub.length()].insert(sub);`
`    ``}`
`    ``for` `(``auto` `it : sorted_subsequence) { `
`        `
`        ``// it.first is length of Subsequence`
`        ``// it.second is set<string>`
`        ``cout << ``"Subsequences of length = "`
`             ``<< it.first << ``" are:"` `<< endl;`
`             `
`        ``for` `(``auto` `ii : it.second)`
`            `
`            ``// ii is iterator of type set<string>`
`            ``cout << ii << ``" "``;`
`        `
`        ``cout << endl;`
`    ``}`
`}`
`// driver function`
`int` `main()`
`{`
`    ``string s = ``"aabc"``;`
`    ``possibleSubsequences(s);`
`    ``return` `0;`
`}`

Output:

```Subsequences of length = 1 are:
a b c
Subsequences of length = 2 are:
aa ab ac bc
Subsequences of length = 3 are:
aab aac abc
Subsequences of length = 4 are:
aabc

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/print-subsequences-string-iterative-method/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Print all subsequences of a strin

Given a string, we have to find out all subsequences of it. A String is a subsequence of a given String, that is generated by deleting some character of a given string without changing its order.

Examples:

```Input : abc
Output : a, b, c, ab, bc, ac, abc

Input : aaa
Output : a, aa, aaa```

Explanation :

```Step 1: Iterate over the entire String
Step 2: Iterate from the end of string
in order to generate different substring
add the subtring to the list
Step 3: Drop kth character from the substring obtained
from above to generate different subsequence.
Step 4: if the subsequence is not in the list then recur.

```

Below is the implementation of the approach.

`// Java Program to print all subsequence of a`
`// given string.`
`import` `java.util.HashSet;`
`public` `class` `Subsequence {`
`    `
`    ``// set to store all the subsequences`
`    ``static` `HashSet<String> st = ``new` `HashSet<>();`
`    ``// It computes all the subsequence of an string`
`    ``static` `void` `subsequence(String str)`
`    ``{`
`        ``// iterate over the entire string`
`        ``for` `(``int` `i = ``0``; i < str.length(); i++) {`
`            `
`            ``// iterate from the end of the string`
`            ``// to generate substrings`
`            ``for` `(``int` `j = str.length(); j > i; j--) {`
`                ``String sub_str = str.substring(i, j);`
`            `
`                ``if` `(!st.contains(sub_str))`
`                    ``st.add(sub_str);`
`                ``// drop kth character in the substring`
`                ``// and if its not in the set then recur`
`                ``for` `(``int` `k = ``1``; k < sub_str.length() - ``1``; k++) {`
`                    ``StringBuffer sb = ``new` `StringBuffer(sub_str);`
`                    ``// drop character from the string`
`                    ``sb.deleteCharAt(k);`
`                    ``if` `(!st.contains(sb))`
`                        ``;`
`                    ``subsequence(sb.toString());`
`                ``}`
`            ``}`
`        ``}`
`    ``}`
`    ``// Driver code`
`    ``public` `static` `void` `main(String[] args)`
`    ``{`
`        ``String s = ``"aabc"``;`
`        ``subsequence(s);`
`        ``System.out.println(st);`
`    ``}`
`}`

Output:

`[aa, a, ab, bc, ac, b, aac, abc, c, aab, aabc]`

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/print-subsequences-string/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Longest subsequence of the form 0*1*0* in a binary string

Given a binary string, find the longest subsequence of the form (0)*(1)*(0)* in it. Basically we need to divide the string into 3 non overlapping strings (these strings might be empty) without changing the order of letters. First and third strings are made up of only 0 and the second string is made up of only 1. These strings could be made by deleting some characters in original string. What is the maximum size of string, we can get?

Examples –

```Input : 000011100000
Output : 12
Explanation :
First part from 1 to 4.
Second part 5 to 7.
Third part from 8 to 12

Input : 100001100
Output : 8
Explanation :
Delete the first letter.
First part from 2 to 4.
Second part from 5 to 6.
Last part from 7.

Input : 00000
Output : 5
Explanation :
Special Case of Only 0

Input : 111111
Output : 6
Explanation :
Special Case of Only 1

Input : 0000001111011011110000
Output : 20
Explanation :
Second part is from 7 to 18.
Remove all the 0 between indices 7 to 18.```

simple solution is to generate all subsequences of given sequence. For every subsequence, check if it is in given form. If yes, compare it with result so far and update the result if needed.

This problem can be efficiently solved by pre-computing below arrays in O(n^2) time.

Let `pre_count_0[i]` be the count of letter 0 in the prefix of string till index i.
Let `pre_count_1[i]` be the count of letter 1 in the prefix of string till length i.
Let `post_count_0[i]` be the count of letter 0 in the suffix string from index i till index n (here n is the size of string).

Now we fix two two positions i and j, 1 <=i <= j <=n. We will remove all 0 from substring which starts at index i and ends in index j. Thus this makes the second substring of only 1. In the prefix before the index i and in the postfix after the index j we will delete all 1 and thus it will make first and third part of the string. then the maximum length of string attainable is max of `pre_count_0[i-1] + (pre_count_1[j]-pre_count_1[i-1]) + pre_count_1[j+1]`

Special cases : When String is made of only 0s or 1s, ans is n where n is length of string.

`// CPP program to find longest subsequence`
`// of the form 0*1*0* in a binary string`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`// Returns length of the longest subsequence`
`// of the form 0*1*0*`
`int` `longestSubseq(string s)`
`{`
`    ``int` `n = s.length();`
`    ``// Precomputing values in three arrays`
`    ``// pre_count_0[i] is going to store count`
`    ``//             of 0s in prefix str[0..i-1]`
`    ``// pre_count_1[i] is going to store count`
`    ``//             of 1s in prefix str[0..i-1]`
`    ``// post_count_0[i] is going to store count`
`    ``//             of 0s in suffix str[i-1..n-1]`
`    ``int` `pre_count_0[n + 2];`
`    ``int` `pre_count_1[n + 1];`
`    ``int` `post_count_0[n + 1];`
`    ``pre_count_0[0] = 0;`
`    ``post_count_0[n + 1] = 0;`
`    ``pre_count_1[0] = 0;`
`    ``for` `(``int` `j = 1; j <= n; j++)`
`    ``{`
`        ``pre_count_0[j] = pre_count_0[j - 1];`
`        ``pre_count_1[j] = pre_count_1[j - 1];`
`        ``post_count_0[n - j + 1] = post_count_0[n - j + 2];`
`        ``if` `(s[j - 1] == ``'0'``)`
`            ``pre_count_0[j]++;`
`        ``else`
`            ``pre_count_1[j]++;`
`        ``if` `(s[n - j] == ``'0'``)`
`           ``post_count_0[n - j + 1]++;`
`    ``}`
`    ``// string is made up of all 0s or all 1s`
`    ``if` `(pre_count_0[n] == n ||`
`        ``pre_count_0[n] == 0)`
`        ``return` `n;`
`    ``// Compute result using precomputed values`
`    ``int` `ans = 0;`
`    ``for` `(``int` `i = 1; i <= n; i++)`
`        ``for` `(``int` `j = i; j <= n; j++)`
`            ``ans = max(pre_count_0[i - 1]`
`                    ``+ pre_count_1[j]`
`                    ``- pre_count_1[i - 1]`
`                    ``+ post_count_0[j + 1],`
`                    ``ans);`
`    ``return` `ans;`
`}`
`// driver program`
`int` `main()`
`{`
`    ``string s = ``"000011100000"``;`
`    ``cout << longestSubseq(s);`
`    ``return` `0;`
`}`

Output :

```Output :20

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/longest-subsequence-of-the-form-010-in-a-binary-string/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Check if two expressions with brackets are same

Given two expressions in the form of strings. The task is to compare them and check if they are similar. Expressions consist of lowercase alphabets, ‘+’, ‘-‘ and ‘( )’.

Examples:

```Input  : exp1 = "-(a+b+c)"
exp2 = "-a-b-c"
Output : Yes

Input  : exp1 = "-(c+b+a)"
exp2 = "-c-b-a"
Output : Yes

Input  : exp1 = "a-b-(c-d)"
exp2 = "a-b-c-d"
Output : No
```

It may be assumed that there are at most 26 operands from ‘a’ to ‘z’ and every operand appears only once.

A simple idea behind is to keep a record of the Global and Local Sign(+/-) through the expression. The Global Sign here means the multiplicative sign at each operand. The resultant sign for an operand is local sign multiplied by the global sign at that operand.

For example, the expression a+b-(c-d) is evaluated as (+)+a(+)+b(-)+c(-)-d => a + b – c + d. The global sign (represented inside bracket) is multiplied to the local sign for each operand.

In the given solution, stack is used to keep record of the global signs. A count vector records the counts of the operands(lowercase Latin letters here). Two expressions are evaluated in opposite manners and finally, it is checked if the all entries in the count vector are zeros.

`// CPP program to check if two expressions`
`// evaluate to same.`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`const` `int` `MAX_CHAR = 26;`
`// Return local sign of the operand. For example,`
`// in the expr a-b-(c), local signs of the operands`
`// are +a, -b, +c`
`bool` `adjSign(string s, ``int` `i)`
`{`
`    ``if` `(i == 0)`
`        ``return` `true``;`
`    ``if` `(s[i - 1] == ``'-'``)`
`        ``return` `false``;`
`    ``return` `true``;`
`};`
`// Evaluate expressions into the count vector of `
`// the 26 alphabets.If add is true, then add count`
`// to the count vector of the alphabets, else remove`
`// count from the count vector.`
`void` `eval(string s, vector<``int``>& v, ``bool` `add)`
`{`
`    ``// stack stores the global sign`
`    ``// for operands.`
`    ``stack<``bool``> stk;`
`    ``stk.push(``true``);`
`    ``// + means true`
`    ``// global sign is positive initially`
`    ``int` `i = 0;`
`    ``while` `(s[i] != ``'\0'``) {`
`        ``if` `(s[i] == ``'+'` `|| s[i] == ``'-'``) {`
`            ``i++;`
`            ``continue``;`
`        ``}`
`        ``if` `(s[i] == ``'('``) {`
`            ``// global sign for the bracket is`
`            ``// pushed to the stack`
`            ``if` `(adjSign(s, i)) `
`                ``stk.push(stk.top());`
`            ``else`
`                ``stk.push(!stk.top());`
`        ``}`
`        ``// global sign is popped out which`
`        ``// was pushed in for the last bracket`
`        ``else` `if` `(s[i] == ``')'``) `
`            ``stk.pop();`
`        `
`        ``else` `{`
`            ``// global sign is positive (we use different `
`            ``// values in two calls of functions so that`
`            ``// we finally check if all vector elements`
`            ``// are 0.`
`            ``if` `(stk.top())                 `
`                ``v[s[i] - ``'a'``] += (adjSign(s, i) ? add ? 1 : -1 : `
`                                                  ``add ? -1 : 1);`
`            ``// global sign is negative here`
`            ``else`
`                ``v[s[i] - ``'a'``] += (adjSign(s, i) ? add ? -1 : 1 : `
`                                                  ``add ? 1 : -1);`
`        ``}`
`        ``i++;`
`    ``}`
`};`
`// Returns true if expr1 and expr2 represent`
`// same expressions`
`bool` `areSame(string expr1, string expr2)`
`{`
`    ``// Create a vector for all operands and`
`    ``// initialize the vector as 0.`
`    ``vector<``int``> v(MAX_CHAR, 0);`
`    ``// Put signs of all operands in expr1`
`    ``eval(expr1, v, ``true``);`
`    ``// Subtract signs of operands in expr2`
`    ``eval(expr2, v, ``false``);`
`    ``// If expressions are same, vector must `
`    ``// be 0.`
`    ``for` `(``int` `i = 0; i < MAX_CHAR; i++) `
`        ``if` `(v[i] != 0) `
`            ``return` `false``;`
`    ``return` `true``;`
`}`
`// Driver code`
`int` `main()`
`{`
`    ``string expr1 = ``"-(a+b+c)"``, expr2 = ``"-a-b-c"``;`
`    ``if` `(areSame(expr1, expr2))`
`        ``cout << ``"Yes\n"``;`
`    ``else`
`        ``cout << ``"No\n"``;`
`    ``return` `0;`
`}`

Output:

```YES

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/check-two-expressions-brackets/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Identify and mark unmatched parenthesis in an expression

Given an expression, find and mark matched and unmatched parenthesis in it. We need to replace all balanced opening parenthesis with 0, balanced closing parenthesis with 1 and all unbalanced with -1.

Examples:

```Input : ((a)
Output : -10a1

Input : (a))
Output : 10a-1

Input  : (((abc))((d)))))
Output : 000abc1100d111-1-1```

The idea is based on stack. We run a loop from the start of the string upto end and for every ‘(‘, we push it into stack. If stack is empty and we encounter an closing bracket ‘)’ the we replace -1 at that index of the strig. Else we replace all opening brackets ‘(‘ with 0 and closing brackets with 1. Then pop from the stack.

`// CPP program to mark balanced and unbalanced`
`// parenthesis.`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`void` `identifyParenthesis(string a)`
`{`
`    ``stack<``int``> st;`
`    ``// run the loop upto end of the string`
`    ``for` `(``int` `i = 0; i < a.length(); i++) {`
`        ``// if a[i] is opening bracket then push `
`        ``// into stack`
`        ``if` `(a[i] == ``'('``) `
`            ``st.push(i);`
`        `
`        ``// if a[i] is closing bracket ')' `
`        ``else` `if` `(a[i] == ``')'``) {`
`            ``// If this closing bracket is unmatched`
`            ``if` `(st.empty()) `
`                ``a.replace(i, 1, ``"-1"``);`
`            `
`            ``else` `{`
`                ``// replace all opening brackets with 0`
`                ``// and closing brackets with 1`
`                ``a.replace(i, 1, ``"1"``);`
`                ``a.replace(st.top(), 1, ``"0"``);`
`                ``st.pop();`
`            ``}`
`        ``}`
`    ``}`
`    ``// if stack is not empty then pop out all`
`    ``// elements from it and replace -1 at that`
`    ``// index of the string`
`    ``while` `(!st.empty()) {`
`        ``a.replace(st.top(), 1, ``"-1"``);`
`        ``st.pop();`
`    ``}`
`    ``// print final string`
`    ``cout << a << endl;`
`}`
`// Driver code`
`int` `main()`
`{`
`    ``string str = ``"(a))"``;`
`    ``identifyParenthesis(str);`
`    ``return` `0;`
`}`

Output:

```0a1-1

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/identify-mark-unmatched-parenthesis-expression/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at