Maximum Repeating Substring

This is an easy level coding interview problem from leetcode. The problem asks you to find the maximum number of repeating string which is given. Please refer to the problem description for more detail. For the solution, you need to iterate the sequence. At each index, you check if the substring matches the word. If it matches, then continue to the next index to find the end of the repeated word. If it doesn’t match, then just move on to the next index.

I provided solutions in C++ and Python3. You can try iterative solution but I provided recursive solutions here. For recursive solutions, it is following the same principles. But note that I keep track of the start index of the comparison because that will be used when the substring doesn’t match.

void maxRepeating(const string &seq, int currIdx, int matchIdx, const string &word, int numRepeat, int &maxRepeat)
{
    // this is base case. make sure you get the max repeat.
    if (seq.size() - matchIdx < word.size())
    {
        maxRepeat = max(maxRepeat, numRepeat);
    }
    // word doesn't match. get the max repeat and then continue comparing the string from the currIdx which is the start of the matching
    else if (seq.substr(matchIdx, word.size()) != word)
    {
        maxRepeat = max(maxRepeat, numRepeat);
        maxRepeating(seq, currIdx + 1, currIdx + 1, word, 0, maxRepeat);
    }
    // word matches. keep checking. make sure currIdx is passed to note the start of the pattern
    else
    {
        maxRepeating(seq, currIdx, matchIdx + word.size(), word, numRepeat + 1, maxRepeat);
    }
}

int maxRepeating(string sequence, string word) {
    int maxRepeat = 0;
    maxRepeating(sequence, 0, 0, word, 0, maxRepeat);
    return maxRepeat;
}
class Solution:
    result = 0
    
    def max_repeating(self, sequence, curr_idx, match_idx, word, num_repeat):
        compare = sequence[match_idx : match_idx + len(word)]
        if len(compare) < len(word):
            self.result = max(self.result, num_repeat)
            return
        elif compare != word:
            self.result = max(self.result, num_repeat)
            self.max_repeating(sequence, curr_idx + 1, curr_idx + 1, word, 0)
            return 
        
        self.max_repeating(sequence, curr_idx, match_idx + len(word), word, num_repeat + 1)
        
    
    def maxRepeating(self, sequence: str, word: str) -> int:
        self.max_repeating(sequence, 0, 0, word, 0)
        return self.result

Longer Contiguous Segments of Ones than Zeros

This is an easy level leetcode problem. Please refer to this link for the detail of the problem description.

Basically, the idea is to find the longest consecutive 1’s and 0’s and return True if 1’s > 0’s.

There are a couple of ways to achieve the problem.

The first one is a pythonic way. Since the string is a binary string that only has 1 and 0, you can split the string based on them. After the split, it’s really to find the longest string in the array. But this solution is only applicable to python.

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        return max((len(digit) for digit in s.split('0'))) > max((len(digit) for digit in s.split('1')))

Another solution is to explicitly iterate the string and count num 1’s and 0’s which are applicable to all other languages. You can do it in one pass as you see the solution below.

class Solution:
    def checkZeroOnes(self, s: str) -> bool:
        ones_start_idx = 0
        num_ones = 0
        zeros_start_idx = 0
        num_zeros = 0
        for idx, digit in enumerate(s):
            if digit == '0':
                ones_start_idx = idx + 1
                num_zeros = max(num_zeros, idx - zeros_start_idx + 1)    
            else:
                zeros_start_idx = idx + 1
                num_ones = max(num_ones, idx - ones_start_idx + 1)
            
            
        return num_ones > num_zeros
        

Delete Characters to Make Fancy String

This is an easy level leetcode problem, which you can use stack to solve.

Please refer to this link for more detail of the problem.

Essentially, you cannot accept 3 or more consecutive duplicate letters. There could be many ways but using a stack seems to be the most elegant approach. Basically, you accumulate each letter if it doesn’t match with the top two entries in the stack or stack has less than 2 elements. This way, you are only accumulating letters that are not duplicate of 3 or more consecutive characters.

class Solution:
    def makeFancyString(self, s: str) -> str:
        fancy = []
        for letter in s:
            if len(fancy) < 2 or fancy[-1] != letter or fancy[-2] != letter:
                fancy.append(letter)
            
        return "".join(fancy)
        

Check Whether Two Strings are Almost Equivalent

This is a leetcode interview problem that requires a hash table with strings. Please refer to this link for more detail of the problem description.

Let me first show you the solution code.

class Solution:
    def checkAlmostEquivalent(self, word1: str, word2: str) -> bool:
        def default_val():
            return list((0, 0))
        count = defaultdict(default_val)
        for letter in word1:
            count[letter][0] += 1
        
        for letter in word2:
            count[letter][1] += 1
            
        for letter, freq in count.items():
            if abs(freq[0] - freq[1]) > 3:
                return False
            
        return True

A hash table is necessary in order to keep track of the frequencies of the letter in the word. Note that I used a list of which size is 2 – the first index is frequencies for word1 and the second index is frequencies for word2.

Once you collected the frequencies, you just need to check if the frequency difference is greater than 3.

Golang – labeled break and continue

break and continue are keywords that control the loop in many programming languages. The scope of those keywords is at inner most. Here is the example code of C++.

for (int i = 0; i < 5; ++i) {
    for (int j = 0; j < 5; ++j) {
        if (i == 1 && j == 3) {
            break;
            // continue;
        }
    }
}

In the example code above, break and continue will only affect the inner most loop which deals with the variable j. However, in golang, you can control the scope of break and continue keyword by using labels.

Here is the example code.

package main

import (
	"fmt"
	"os"
	"strings"
)

func main() {
	library := `
	I am learning computer science and computer engineering
	`
	words := strings.Fields(library)
	query := os.Args[1:]

queries:
	for _, q := range query {
		for i, w := range words {
			if q == w {
				fmt.Printf("index %d: %q\n", i, w)
				break queries
			}
		}
	}
}

Let’s say there is a library of words and you are querying unique words. For example, when you query the word computer, it should return the first index of the word and the word itself. As you are running the loop, there are multiple ways to achieve this. But I want to show you that you can use a label to control the scope. You can declare the label at any scope you want and use the label with break or continue keyword. As you see in the above code, it will exit the entire thing once it finds the word.

go run main.go computer
index 3: "computer"

Go Lang – Printf Cheat Sheet

This is a go lang Printf cheat sheet post. Essentially it is very similar to the one in C. Just like the one in C, Printf really prints the string in a formatted way. It is very convenient to have a cheat sheet since I always forget unless I use it frequently. This mainly focuses on examples.

print type of variable %T

var intNum int
var floatNum float64
var boolVal bool
var strVal string

fmt.Printf("%T\n", intNum)
fmt.Printf("%T\n", floatNum)
fmt.Printf("%T\n", boolVal)
fmt.Printf("%T\n", strVal)

// output
int
float64
bool
string

print int type %d

This prints integer type. It will perform type check and will give you a warning that type doesn’t match. And of course the result format will be odd.

age := 21
fmt.Printf("age: %d\n", age)
fmt.Printf("age: %s\n", age)

// output
age: 21
age: %!s(int=21)

print float %f

%f prints floating numbers. Since this is a floating number, you can control the precision with “.<number>”
Increasing precision means the floating number will be more precise.

floatNum := 224.701
fmt.Printf("num: %f\n", floatNum)
fmt.Printf("num: %.0f\n", floatNum)
fmt.Printf("num: %.1f\n", floatNum)
fmt.Printf("num: %.2f\n", floatNum)
fmt.Printf("num: %.3f\n", floatNum)
fmt.Printf("num: %.4f\n", floatNum)
fmt.Printf("num: %.5f\n", floatNum)

// output
num: 224.701000
num: 225
num: 224.7
num: 224.70
num: 224.701
num: 224.7010
num: 224.70100

print bool %t

male := true
female := false

fmt.Printf("are you male?: %t\n", male)
fmt.Printf("are you femail?: %t\n", female)

//output
are you male?: true
are you femail?: false

print string type %s, %q

Those print the strings. However, there is a difference between them. %s just prints the string itself but %q prints with double quotes.
Note that \n is just an escape sequence providing a new line. This also performs type checks.

name := "Google"
fmt.Printf("%s\n", name)
fmt.Printf("%q\n", name)

// output
Google
"Google"

print any value %v

This prints all the provided values. It’s very convenient but it doesn’t guarantee any type safety. For example, what if you only want to print int instead of string or float? %v will not check anything and print as-is.

name := "Google"
val := 1
floatVal := 1.123
fmt.Printf("%v %v %v\n", name, val, floatVal)

// output
Google 1 1.123

Argument Index

Typically you have to provide a value for each verb in the Printf format string. However, there is an exception to this rule. You can refer to the already provided variable. This is called argument index. Note that [1] refers to the first argument which is “name”. [2] refers to the second argument. Why does the index start from 1? It’s because index 0 of the Printf is the format string.

name := "NY Comdori"
job := "software engineer"

fmt.Printf("%v is a %v. Being %[2]v is fun! Good luck %[1]v!\n", name, job)

// output
NY Comdori is a software engineer. Being software engineer is fun! Good luck NY Comdori!

Go lang – iota and constants

In programming languages such as C++ and Java, there is Enum type which is used frequently. In go language, you can use iota to represent an Enum type.

Let’s take a look at a simple example

Example

Let’s say you want to define variables to represent weekdays. In that case, you probably just want to have integer values for a simple comparison. (You really don’t want to use string to represent the value unless you are printing) Let’s take a look at a version that naively represents the weekdays.

const (
	SUNDAY = 0
	MONDAY = 1
	TUESDAY = 2
	WEDNESDAY = 3
	THURSDAY = 4
	FRIDAY = 5
	SATURDAY = 6
)

// output
fmt.Println(SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY)

0 1 2 3 4 5 6

Now it will perfectly fine because you can use those variables like others. However, it is very tedious to explicitly type all the values because you really don’t care about those. You just want consecutive integers. Here is where iota comes into play to make life better.

What is iota? It is a built-in constant generator that generates consecutively increasing numbers. Let’s take a look at the usage

const (
	SUNDAY = iota
	MONDAY
	TUESDAY
	WEDNESDAY
	THURSDAY
	FRIDAY
	SATURDAY
)

// output
fmt.Println(SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY)

0 1 2 3 4 5 6

With iota, you only need to assign iota once to the place you want to generate. iota always starts from 0 and will increase the number and repeat the same assignment as the previous line. In the example above, SUNDAY will be 0. For MONDAY, iota will repeat itself with the increased number which is 1. It will stop once it reaches the end and the value will be reset to 0 so that it won’t disrupt other constant settings. What happens if you want to use iota from the middle part?

const (
	SUNDAY = -1
	MONDAY = iota
	TUESDAY
	WEDNESDAY
	THURSDAY
	FRIDAY
	SATURDAY
)

// output
fmt.Println(SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY)
-1 1 2 3 4 5 6

You just have to explicitly set the value before the iota usage. iota will start from there. Note that iota value starts from 1 instead of 0.
Why is that? It’s because iota starts from the beginning of the constants.

Blank Identifier

You can use a formula to set a custom value using iota. iota always starts from 0 and if you want a different value, you have to use some expression to do that. Let’s say you want to represent different timezones in constants. You only want to represent three timezones in the U.S. – EST, MST, PST – compared to UTC. For example, EST means the eastern standard time that is -5 hours behind UTC. MST means mountain time that is -7 hours behind UTC. PST means the pacific time that is -8 hours behind UTC. Therefore you want to have your constants represent like this.

const (
	EST = -5
	MST = -7
	PST = -8
)

fmt.Println(EST, MST, PST)
-5 -7 -8

But how can you use iota here? There are two issues here. iota will return a non-negative increasing number but you want to have negative numbers here. The second issue is that the values we want are not consecutive. Let’s tackle the issue one by one. How can we have negative numbers using iota? We can use a formula to manipulate the value.

const (
	EST = -(iota + 5)
	MST
	PST
)

fmt.Println(EST, MST, PST)
-5 -6 -7

You can use a typical mathematical expression when using iota because it just returns a number.

Now, there is still an issue here. We want -5, -7, -8 but actually got -5, -6, -7 because iota only returns consecutively increased numbers. What can we do? Remember that iota will always increase the value in every line. But We certainly don’t want to declare any dummy constant just for that. Blank identifier comes to the rescue. Blank identifier in go is to tell the compiler this is unused variable and ignore it. It is ‘_’.

const (
	EST = -(iota + 5)
	_
	MST
	PST
)

fmt.Println(EST, MST, PST)
-5 -7 -8

Now, note that iota will increase by 1 at line 3. We all know that ‘_’ is a dummy and can just ignore. In MST, it will be set to -7 which is the correct value now.

Conclusion

We have briefly taken a look at iota and constants in go lang. It could be pretty convenient when used properly. Happy coding!

Intro to CSS Grid Layout Part 5

This is intro to CSS grid layout part 5. So far we have taken a look at following topics. It is recommended to take a look if you are not familiar with css grid layout basics.

In this post, I will focus on explaining how to use grid area with area names for positioning grid items with an example. Let’s take a look it.

Example

We have a layout of multiple items. Note that the header is not spanning to the end but the last slot is empty.

HTML Code

This is the html code used for the example

<div class="challenge">
  <div class="header">Header</div>
  <div class="small-box-1">Small box</div>
  <div class="small-box-2">Small box</div>
  <div class="small-box-3">Small box</div>
  <div class="main-content">Main content</div>
  <div class="sidebar">Sidebar</div>
  <div class="footer">Footer</div>
</div>


CSS Code

We have 4 rows and 4 columns which make 16 unit areas. To use area based positioning, you need to define each unit area with an area name. You can decide the name as you prefer. As you can see, grid-template-areas property is defined with 16 names. For example, head is located at the first row and spanning from first to third column. “.” represents an empty slot. After you define the area representation, all you need to do is to specify the area name for each class. Take a look at line 21 and others.

.challenge {
  width: 1000px;
  margin: 30px auto;
  
  display: grid;
  grid-template-rows: 100px 200px 400px 100px;
  grid-template-columns: repeat(3, 1fr) 200px;
  grid-gap: 35px;
  grid-template-areas: "head head head ."
                      "small-box-1 small-box-2 small-box-3 side"
                      "main main main side"
                      "foot foot foot foot";
  
  & > * {
    background-color: orangered;
    padding: 15px;
    color: white;
    font-size: 30px;
    font-family: sans-serif;
  }
  .header {
    grid-area: head;
  }
  
  .small-box-1 { grid-area: small-box-1; }
  .small-box-2 { grid-area: small-box-2; }
  .small-box-3 { grid-area: small-box-3; }
  
  .sidebar {
    grid-area: side;
  }
  
  .main-content {
    grid-area: main;
  }
  
  .footer {
    grid-area: foot;
  }
}

It is very important to note that you have to have a complete area representation. Since you have 16 unit slots (4 rows * 4 columns), you have to have 16 area names in order to use it. It is fairly simple to use for a simple area layout. However, if you have a complex layout, it could be inconvenient to use it. i.e., 10 rows and 10 columns. In such a case, it would be better to use grid lines instead of names.

Intro to CSS Grid Layout Part 4

This is intro to CSS grid layout part 4 continuing from previous posts. This will specifically focus on how to position grid items based on the name of the grid lines. If you are not familiar with CSS grid layout, please refer to these posts here.

In the previous post, we went over how to position grid items based on their grid line numbers. However, it is often hard to read and understand the code when it’s using line numbers. To improve the readability and maintainability, we want to use names for the line numbers. Let’s take a look at them now.

Example

This is the one we are going to build using CSS grid layout.

HTML Code

<div class="challenge">
  <div class="header">Header</div>
  <div class="small-box-1">Small box</div>
  <div class="small-box-2">Small box</div>
  <div class="small-box-3">Small box</div>
  <div class="main-content">Main content</div>
  <div class="sidebar">Sidebar</div>
  <div class="footer">Footer</div>
</div>


CSS Code

.challenge {
  width: 1000px;
  margin: 30px auto;
  
  display: grid;
  grid-template-rows: [header-start] 100px [header-end box-start] 200px [box-end main-start] 400px [main-end footer-start] 100px [footer-end];
  grid-template-columns: repeat(3, [col-start] 1fr [col-end]) 200px [grid-end];
  grid-gap: 35px;
  
  & > * {
    background-color: orangered;
    padding: 15px;
    color: white;
    font-size: 30px;
    font-family: sans-serif;
  }
  .header {
    grid-column: col-start 1 / grid-end;
  }
  
  .sidebar {
    grid-column: col-end 3 / grid-end;
    grid-row: box-start / main-end;
  }
  
  .main-content {
    grid-column: col-start 1 / col-end 3;
  }
  
  .footer {
    grid-column: col-start 1 / grid-end;
  }
}

Let’s first take a look at how grid-template-rows and grid-template-columns are defined. Typically, you would just list width of each row and column and use the line number. However, in each line number position, you can have a list of names to use instead of numbers.

Name for grid-template-rows

Note that row line number 1 is before the first row which is now named header-start. Now, row line number 2 could have multiple names because it is the position where header ends but all other boxes start. That’s why we also added a name box-start at row line number 2. You can follow the similar logic for all other row numbers.

grid-template-rows: [header-start] 100px [header-end box-start] 200px [box-end main-start] 400px [main-end footer-start] 100px [footer-end];

Name for grid-template-columns

There is a difference for columns because it uses repeat with fractional units. Just putting the name before and after the repeat would be incorrect because it will not put names between those columns. We put names in the repeat keyword like this: repeat(3, [col-start] 1fr [col-end]). It means I want to put a name before and after 1fr column. In order to prevent any name conflict, CSS will automatically add numbers starting from 1.

grid-template-columns: repeat(3, [col-start] 1fr [col-end]) 200px [grid-end];

Usage

Now you can define all element classes using names instead of line numbers. I am only going to note one class as an example here. As you can see sidebar class, it is using names. Since the sidebar is the end column of the grid, it uses col-end 3 and grid-end (3 is automatically added by CSS). The row uses box-start and main-end.

.sidebar {
  grid-column: col-end 3 / grid-end;
  grid-row: box-start / main-end;
}


Conclusion

It is very simple to use names instead of line numbers when positioning grid items. And it is actually recommended practice. In the next post, I will explain how to position grid items based on grid area using names.

Intro to CSS Grid Layout Part 3

This is a continuation of intro to css grid layout articles. Please refer to previous articles for declaring grid layout and fractional units in row/column. This post will specifically focus on the positioning and spanning of the grid item. Let’s take a look at the example image and code first.

Example

HTML Code

<div class="container">
  <div class="item item--1">1: Orange</div>
  <div class="item item--2">2: Green</div>
  <div class="item item--3">3: Violet</div>
  <div class="item item--4">4: Pink</div>
  <div class="item item--5">5: Blue</div>
  <div class="item item--6">6: Brown</div>
</div>

As you see in the above image and the HTML code, each item is placed in the order of declaration which is the default positioning of the CSS grid layout. Then, you might ask a question if it’s possible to place an item to a specific location. For example, how do you place the item 1: orange to the location of 5: blue? There are CSS properties that allow you to change the position.

CSS Code

.container {
  background-color: #eee;
  width: 1000px;
  margin: 30px auto;
  
  display: grid;
  grid-template-rows: repeat(2, 150px);
  grid-template-columns: repeat(3, 1fr);
  grid-gap: 60px;
}

.item {
  padding: 20px;
  font-size: 30px;
  font-family: sans-sarif;
  color: white;
  
  &--1 {
    background-color: orangered;
    grid-row-start: 2;
    grid-row-end: 3;
    grid-column-start: 2;
    grid-column-end: 3;
    /*grid-row: 2 / 3;*/
    /*grid-column: 2 / 3;*/
  }
  
  &--2 {
    background-color: green;
  }
  
  &--3 {
    background-color: violet;    
  }
  
  &--4 {
    background-color: pink;
  }
  
  &--5 {
    background-color: blue;
  }
    
  &--6 {
    background-color: brown;
  }
}

Take a look at lines 20-23 in the CSS code. You have two choices to change the position.
1. use grid-<row/column>-<start/end>
2. use grid-<row/column> which is a short hand version

Do you remember there are row/column line numbers when you have CSS Grid? If you are not familiar with the concept, please refer to this article. Basically, there are row/column line numbers and you just need to specify row/column start/end position based on the number.

Looking at the image there are 3 row lines: start of the row grid, middle of the row grid and end of the row grid (1,2,3). There are 4 lines in the column: start of the column grid, 2 middle lines, end of the column grid. After specifying row/column start/end points you will notice that item 1 is now placed where item 5 was.

There are shorthand version of specifying row/column start/end which are commented at line 24,25. There is another shorthand version which is using grid-area but I think it is not really readable and didn’t specify here. You can take a look at the documentation for that.

What if more than one items are to be placed on the same position? Simply the last one will be rendered on top of the first one. The first item will not be shown.

What if you put multiple rows or columns in the grid-row or grid-column? It will simply span to take the specified area. Note that grid-column now has start at 2 and end at 4 which should take space from column 2 to 4.

  &--1 {
    background-color: orangered;
    grid-row: 2 / 3;
    grid-column: 2 / 4;
  }

Note that item 6 is now pushed to new row because item 1 is taking up the space. Even though we only specified 2 rows, CSS grid automatically expands to fit the items which is called implicit grid I will discuss in different post.

Another way of specifying the span is like this. Note that instead of specifying the end column in line 4, you can tell how many lines it should span in this case 2. Another special usage is putting -1 (at line 7) which means to span to the end of the columns.

  &--1 {
    background-color: orangered;
    grid-row: 2 / 3;
    grid-column: 2 / span 2;
    
    /*
    grid-column: 2 / -1;
    */
    
  }

Conclusion

We have taken a look at positioning of the grid item. In next post, I am going to explain how to name grid line numbers to improve readability.