# Day 2 of LeetCode Challenge

# Problem 1: Lexicographically Smallest Palindrome

[link to the problem](https://leetcode.com/problems/lexicographically-smallest-palindrome/description/)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1740838399708/0d0e714f-b1c1-480d-917f-0e189242b166.png align="center")

```python
class Solution {
    public String makeSmallestPalindrome(String s) {

        if(s.length()==1)
            return s;

        for(int i=0; i<s.length()/2; i++){
            if(s.charAt(i)!=s.charAt(s.length()-i-1)){
                char ch = s.charAt(i)<s.charAt(s.length()-i-1)?s.charAt(i):s.charAt(s.length()-i-1);
                s=s.substring(0,i)+ch+s.substring(i+1, s.length()-i-1)+ch+s.substring(s.length()-i);
            }
        }
        
        return s;
    }
}
```

---

# Problem 2: Valid Permutations for DI Sequence

[link to the problem](https://leetcode.com/problems/valid-permutations-for-di-sequence/)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1740922507047/c3eb47ad-6692-4819-be7e-8cb5969314b9.png align="center")

```python
class Solution {
    boolean[] vis;
    Integer[][] memo;
    int mod = (int)1e9+7;
    public int numPermsDISequence(String s) {
        vis = new boolean[s.length()+2];
        memo = new Integer[s.length()][s.length()+3];
        return solve(s,0,-1);
    }
    private int solve(String s,int idx,int prev){
        if(idx >= s.length()){
            return 1;
        } else if(memo[idx][prev+1] != null){
            return memo[idx][prev+1];
        }

        int cnt = 0;
        for(int i=0;i<=s.length();i++){
            if(!vis[i]){
                vis[i] = true;
                if(prev == -1){
                    cnt = (cnt + solve(s,idx,i)) % mod;
                } else if((s.charAt(idx) == 'D' && i < prev) 
                    || s.charAt(idx) == 'I' && i > prev){
                        
                    cnt = (cnt + solve(s,idx+1,i)) % mod;
                }
                vis[i] = false;
            }
        }

        return memo[idx][prev+1] = cnt;
    }
}
```

---

# Problem 3: Race Car

[link t](https://leetcode.com/problems/race-car/)[o the problem](https://leetcode.com/problems/race-car/description/)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1740924767467/6f5bf3ff-29df-46c7-8ff9-e00c3f8775ff.png align="center")

```python
class Solution {
   List<Integer[]> queue = new ArrayList<Integer[]>(); 
   HashSet<Integer[]> visited = new HashSet<Integer[]>(); 
   int moves, position, speed = 0;
    public int racecar(int target) {
          queue.add(new Integer[]{0,0,1}); 
          
          while(queue.size() > 0) {
              moves = queue.get(0)[0];
              position = queue.get(0)[1];
              speed = queue.get(0)[2];
              queue.remove(0);
              
              if (position == target) {
                  return moves;
              } else if (visited.contains(new Integer[]{position, speed})) {
                  continue;
              }
              else {
              visited.add(new Integer[]{position, speed});
                  queue.add(new Integer[]{moves+1,position+speed,speed*2 });
                  if ((position+speed > target && speed > 0) || (position+speed < target && speed < 0)) {
					  queue.add(new Integer[]{moves+1,position, speed > 0? -1: 1 });
                  }
              }
          }
        return moves;
    }
}
```

---

# Problem 4: Maximum Number of Fish in a Grid

[link to the problem](https://leetcode.com/problems/maximum-number-of-fish-in-a-grid/)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1740925941718/1c79def6-6233-4f09-bf1b-154d94a9b7fe.png align="center")

```python
class Solution {
    int[][] directions={ {0,1},{0,-1}, {1,0},{-1,0} };
    boolean[][] visited;
    
    public int findMaxFish(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int maxFish=0;       

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]==0) continue;
                
                visited=new boolean[m][n];
                               
                maxFish=Math.max(maxFish, dfs(grid, i, j, m, n));
            }
        }

        return maxFish;
    }

    int dfs(int[][] grid, int i, int j, int m, int n){
        visited[i][j]=true;
        int fish=0;
        
        if(grid[i][j]==0) return fish;

        fish+=grid[i][j];
        for(int[] dir:directions){
            int nr=i+dir[0];
            int nc=j+dir[1];
            if(nr>=0 && nr<m && nc>=0 && nc<n){
                if(!visited[nr][nc]){                           
                    fish+=dfs(grid, nr, nc, m, n);
                }
            }
        } 

        return fish;
    }

}
```

---

# Problem 5: Construct the Longest New String

[link to the problem](https://leetcode.com/problems/camelcase-matching/description/)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1741108805737/dbcfe6ea-d73c-449a-ab5c-efc86a0d3dc6.png align="center")

```python
class Solution {
    public List<Boolean> camelMatch(String[] queries, String pattern) {
      List<Boolean> list = new ArrayList<>();

      for (var q : queries) {
         int index = 0;
         boolean flag = true;
         for (var c : q.toCharArray()) {
            if(index < pattern.length() && c == pattern.charAt(index)){
               index++;
               continue;
            }
            if(c >= 'A' && c <= 'Z'){
               if(index >= pattern.length() || c != pattern.charAt(index)){
                  flag = false;
                  break;
               }
            }
         }
         flag = flag && index == pattern.length();
         list.add(flag);
      }
      return list;
    }
}
```